滑雪板分组与最小夹板长度

共有 n 块滑雪板，第 i 块滑雪板的重量为 Gi，长度为 Li。需要将全部滑雪板分成若干组装入木箱。

每组必须满足：组内滑雪板重量总和不超过包裹最大承重 G。每个木箱需要两根夹板，夹板长度等于该组内最长滑雪板的长度。

请合理分组，使所有木箱所需夹板的总长度最小。

输入格式

第一行输入两个整数 n、G，分别表示滑雪板数量和单个木箱的最大承重。

接下来 n 行，每行输入两个整数 Gi、Li，表示一块滑雪板的重量和长度。

输出格式

输出一个整数，表示最小夹板总长度。

数据范围

• 1 ≤ n ≤ 9；
• 1 ≤ Gi ≤ G ≤ 30；
• 1 ≤ Li ≤ 100；
• 每块滑雪板都可以单独装入一个木箱；
• 每组木箱需要 2 根夹板。

子任务

• 子任务 1（15 分）：n ≤ 3。
• 子任务 2（25 分）：n = 5，包含样例数据。
• 子任务 3（30 分）：n ≤ 7。
• 子任务 4（30 分）：n = 9，需要在较严格时间限制内完成状态搜索。

样例

输入

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

输出

10

样例说明

一种最优分组为：

• 重量 1、长度 3；重量 2、长度 3；重量 2、长度 2；
• 重量 1、长度 2；重量 2、长度 1。

两组的最长长度分别为 3 和 2，夹板总长度为：

3 + 2 × 2 = 10