유로비전

올해 유로비전은 개최지로 뽑힌 델프트의 Aula에서 열린다. 표는 몇 초 만에 모두 매진되었다. 델프트 각 학부의 학생들이 행사에 참석하고 싶어 하며, 그들은 같은 질문을 던지고 있다. 참가자가 최적으로 숨을 쉴 때, 숨을 쉬지 않고 노래해야 하는 가장 긴 시간은 얼마인가?

노래는 $n$개의 음악 구간으로 나뉜다. $i$번째 구간의 음높이 강도는 $a_i$이고, 길이는 $b_i$초이다. 참가자는 구간을 쉬지 않고 차례로 부르지만, 특정 순간에 숨을 쉰다. 숨을 쉬는 데 걸리는 시간은 무시할 만큼 짧다. 참가자는 음높이 강도의 극솟값 직후에만 숨을 쉰다. 즉 $1 < i < n$이고 $a_{i-1} > a_i < a_{i+1}$인 구간 $i$의 직후이다. 참가자가 쉬는 횟수는 전부 합쳐 $k$번을 넘지 않는다.

참가자는 최적으로 숨을 쉰다. 주어진 제약 안에서 두 번의 숨 쉬기 사이의 가장 긴 시간이 가능한 한 짧아지도록 쉰다.

가수는 노래를 시작하기 직전과 끝낸 직후에 숨을 쉰다. 이 두 번의 숨은 전체 횟수에 포함되지 않는다.

입력은 다음과 같다.

• 첫 줄에 두 정수 $n$ ($1\leq n\leq 10^4$)과 $k$ ($0\leq k < n$)가 주어진다. $n$은 음악 구간의 개수이고, $k$는 노래 중 쉴 수 있는 최대 횟수이다.
• 이어서 $n$개의 줄에 각각 두 정수 $a_i$와 $b_i$ ($1 \leq a_i, b_i \leq 10^9$)가 주어진다. 각각 $i$번째 구간의 음높이 강도와 길이(초)이다.

최적으로 노래했을 때, 두 번의 숨 쉬기 사이의 가장 긴 시간을 초 단위로 출력한다.