#8801. 「2023年杭州智力运动会」奶牛的破坏力 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wind_Rises

题目描述

农场里有N头奶牛,站在一条直线上,每头奶牛的位置均不同,且每头奶牛都有一定的破坏力为了管理农场秩序,约翰想修建一道围栏,由于预算有限,约翰只能修建长

度不超过 的围栏因此。约翰想寻找一种策略,希望约束住的奶牛破坏力总和尽量的大,你能帮帮他么?

输入格式

第一行输入两个正整数: ,分别表示奶牛的总数和围栏的长度。接下来输入 行,每行两个整数,分别表示奶牛的位置 和奶牛的破坏力

(位置按从左到右的顺序输入)。

输出格式

输出最大的破坏力总和。

样例

样例输入

复制5 4
1 2
3 3
5 1
8 5
10 4

样例输出

数据范围与提示