6012 - 滑雪板打包问题

通过次数

1

提交次数

1

Time Limit : 1 秒
Memory Limit : 128 MB

厂家接到一家新开业的滑雪场采购不同规格滑雪板的订单，每个滑雪板的长度是不固定的，现在需要把若干个滑雪板用木板打包好进行快递，每个快递的重量是有限制的，不能超过重量G。只要每次打包的重量不超过G，多个滑雪板可以摞放在一起，使用与最长滑雪板长度相同的2块木板进行固定。现在给出每个滑雪板的重量G_i和长度L_i，请计算至少需要多长的木板才能将所有的滑雪板打包好。

Input

第一行2个用空格隔开的n，m，n是滑雪板数量，m是一个包裹的最大重量(0 < n <= 10^4，0 < m < = 10^5)
之后共n行数据，每行是2个用空格隔开的数字G_i和L_i(0 < G_i <= m，0 < L_i < = 10^3)，分别是某只滑雪板的重量和长度

Output

最小的木板长度

Examples

Input

5 5
2 1
1 2
1 3
2 3
2 2

Output

10

Input

7 6
3 1
1 2
2 3
2 3
2 2
1 1
1 1

Output

10

Hint

注：每次打包需要2块木板

Source

信息素养大赛-2023-智能算法C++挑战复赛

上一题 下一题
请先登陆