农场里有N头奶牛,站在一条直线上,每头奶牛的位置均不同,且每头奶牛都有一定的破坏力为了管理农场秩序,约翰想修建一道围栏,由于预算有限,约翰只能修建长
度不超过 的围栏因此。约翰想寻找一种策略,希望约束住的奶牛破坏力总和尽量的大,你能帮帮他么?
第一行输入两个正整数: 和 ,分别表示奶牛的总数和围栏的长度。接下来输入 行,每行两个整数,分别表示奶牛的位置 和奶牛的破坏力。
(位置按从左到右的顺序输入)。
输出最大的破坏力总和。
样例输入
复制5 4 1 2 3 3 5 1 8 5 10 4
5 4 1 2 3 3 5 1 8 5 10 4
样例输出
复制9
9