Given a sequence of ordered pairs of positive integers , you have to partition it into several contiguous parts. Let be the number of these parts, whose boundaries are , which satisfy li = ri − 1 + 1, , ,. The parts themselves also satisfy the following estrictions:
For any two pairs , , where is belongs to the th part and the th part. If , then .
Let be the maximum of elements in the th part, say
it is provided that
where is a given integer.
Let be the sum of of elements in the th part. Now I want to minimize the value
Could you tell me the minimum?
输入格式
The input contains exactly one test case.
The first line of input contains two positive integers .
Then follow lines each contains a positive integers pair . It's always guaranteed that 。
输出格式
Output the minimum target value.
样例
样例输入 #1
4 6
4 3
3 5
2 5
2 4
样例输出 #1
9
样例解释
An available assignment is the first two pairs are assigned into the first part and the last two pairs are assigned into the second part. Then , and minimum .
