滑雪板打包问题

题目描述

一家新开业的滑雪场需要采购不同规格的滑雪板，每个滑雪板的长度是不固定的。现在需要把排列好的滑雪板用木板做成木箱封装好进行快递，每次快递的总重量是有限制的，不能超过重量 G。只要每次打包的重量不超过 G，多个滑雪板可以摞放在一起，使用与最长滑雪板长度相同的两个木板进行固定。

给定排列好的每个滑雪板的重量 Gi 和长度 Li，请计算需要最少多长的木板才能将所有的滑雪板打包好。 数据范围：不大于n不大于2000。

输入格式

• 第一行有两个数字：
  n（滑雪板的个数）
  G（包裹总重量限制）
• 接下来 n 行，每行两个整数：
  Gi（滑雪板重量）
  Li（滑雪板长度）

输出格式

输出需要的最少木板总长度（每次打包需要 2 个木板）。

样例 #1

样例输入 #1

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

样例输出 #1

10