该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

货舱装载计划

题目描述

某科研队即将进行一次外星勘测任务。出发前，基地准备了 $N$ 件可携带的研究设备。第 $i$ 件设备可以为任务带来贡献值 $a_i$，同时会占用货舱容量 $b_i$。

飞船货舱的总容量上限为 $C$。科研队需要从这些设备中选择若干件装入货舱，使得被选择设备的总占用容量不超过 $C$，并让总贡献值尽可能大。

每件设备最多只能选择一次。

请你计算，在容量限制内能够获得的最大总贡献值。

输入格式

第一行包含两个整数 $N$ 和 $C$（$1 \leq N \leq 200,\ 1 \leq C \leq 10^9$），表示设备数量和货舱容量上限。

接下来 $N$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i,b_i \leq 10^9$），表示第 $i$ 件设备的贡献值和占用容量。

为了覆盖不同规模的数据，测试数据保证至少满足以下三种情况之一：

• 设备数量较少，即 $N \leq 30$；
• 所有设备占用容量较小，即对所有 $1 \leq i \leq N$，都有 $b_i \leq 1000$；
• 所有设备贡献值较小，即对所有 $1 \leq i \leq N$，都有 $a_i \leq 1000$。

也就是说，虽然容量和贡献值的上限可能很大，但每组测试数据都会在“设备数量”“占用容量”或“贡献值”三者之一上具有可利用的限制。

输出格式

输出一个整数，表示在不超过货舱容量上限的前提下，可以获得的最大总贡献值。

输出后换行。

输入输出样例 #1

输入 #1

4 12
8 5
10 6
7 4
6 3

输出 #1

21