FPC22-006.Eurovision

It's that time of the year! Time again for Eurovision (and FPC)! Although, there is something rather special about this edition. In an unexpected turn of events, Delft was chosen to host Eurovision in the Aula. As you might expect, all tickets were sold out in a matter of seconds: students from all over Delft's faculties are eager to attend such a special event. Naturally, their enthusiasm is sparked by the same question: “What's the longest time a contestant has to sing without breathing, given that they breathe optimally?”

A song is divided into $n$ musical segments, where the $i$th musical segment has pitch intensity $a_i$ and is $b_i$ seconds in length. Each contestant sings these musical segments consecutively, with no pause in between, but will take some deep breaths at key moments (consider the time it takes to breathe negligible). To maintain a pleasing rhythm of music, performers only breathe immediately after a local minimum in pitch intensity (i.e., after a musical segment $i$ where $a_{i-1} > a_i < a_{i+1}, 1 < i < n$) and do not take more than $k$ breaths in total.

Note:

• Eurovision contestants have an inclination towards algorithmic thinking, and therefore, they all breathe optimally: within the constraints, the longest time between two breaths is as short as possible.

• Naturally, a singer will breathe right before starting to sing and immediately after finishing, so these two breaths do NOT count towards the total number of breaths.