题目描述

在一条街道上有$n$栋楼，第$i$栋有$h_i$层，每层都有价值为$v_i$的物品。 Lyra可以花费一单位时间在同一栋楼中向上或向下走一层。特别地，每栋楼里都有一个大滑梯，只能从顶楼通往一楼，所以如果Lyra在顶层，可以花费一单位时间通过滑梯到达一楼（注意只有在顶楼才可以使用滑梯）。 Lyra还可以在不同的楼之间跳跃，即花费一单位时间从当前楼移动到相邻楼的同层，如果相邻楼没有Lyra当前位置高，则会落到相邻楼的顶层。 初始时Lyra在第一栋楼的顶层，她有$m$单位时间可以移动，Lyra拿去物品不需要时间，且一个物品被拿一次之后就会消失。 Lyra想知道她能获得的总价值最多是多少？

输入

第一行两个正整数$n,m$。 以下$n$行每行两个整数表示$h_i$和$v_i$。 提示：输入数据较大，请采用快速的读入方式。

输出

输出一行一个整数表示最大的总价值。

输入样例

3 3
2 1
1 5
3 4

输出样例

14

提示

【数据规模及约定】 对于20%的数据，$Σh_i≤20$。 对于另外10%的数据，$v_i=1$。 对于另外30%的数据，$Σh_i≤1000$。 对于另外20%的数据，$n,h_i≤10^5$。 对于100%的数据，$n,h_i≤10^6$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。