Eurovision

Time limit1sMemory limit2048 MB

Summary

Given segments with pitch and duration, pick at most k breath points after local minima to minimize the longest breath-free stretch in seconds.

Level: Medium6 of 10
Topics: Binary search, Greedy, Array
Solved: No attempts yet

Statement

Eurovision is held in the Aula in Delft this year, since Delft was chosen as the host. All tickets sold out within seconds. Students from all of Delft's faculties want to attend, and they are asking the same question: what is the longest time a contestant has to sing without breathing, if the contestant breathes optimally?

A song is divided into $n$ musical segments. The $i$ th segment has pitch intensity $a_i$ and lasts $b_i$ seconds. A contestant sings the segments one after another with no pause in between, but takes breaths at certain moments. Breathing takes negligible time. A contestant breathes only immediately after a local minimum in pitch intensity, meaning after segment $i$ with $1 < i < n$ and $a_{i-1} > a_i < a_{i+1}$ . A contestant takes at most $k$ breaths in total.

Contestants breathe optimally: within the constraints, the longest time between two breaths is as short as possible.

A singer breathes right before starting and right after finishing. These two breaths do not count toward the total number of breaths.

Input

The input consists of:

One line containing two integers: $n$ ( $1\leq n\leq 10^4$ ), the number of musical segments, and $k$ ( $0\leq k < n$ ), the maximum number of breaths.
$n$ lines each containing two integers $a_i$ and $b_i$ ( $1 \leq a_i, b_i \leq 10^9$ ), the pitch intensity and length in seconds of the $i$ th segment.

Output

Output the longest time in seconds between two breaths for an optimal performance.

Examples2

Example 1
Input
```
6 1
1 1
2 1
1 1
2 1
1 1
2 1
```
Expected output
```
3
```

Example 2

Input

Expected output