g6-07984. 天平称重 未做

实验室有一架天平和 $n$ 个砝码，第 $i$ 个砝码重 $w_i$、精美度 $a_i$（用来评估展览价值）。天平的托盘最多承重 $C$，而 $C$ 与砝码重量 $w_i$ 都可达 $2^{30}$；每个砝码至多放一次，且 $n\le 30$、$a_i\le 500$，所有砝码的精美度总和不超过 $15000$。请选出一些砝码放进托盘，使总重量不超过 $C$，并让精美度总和最大。

第一行两个整数 $n,C$。

接下来 $n$ 行，每行两个整数 $w_i,a_i$。

一行一个整数，表示最大精美度总和。

输入 1

3 1073741824
1073741824 100
1073741823 100
1073741822 100

输出 1

100

任取两个的总重都超过 $C=2^{30}$，只能放一个砝码，精美度 100。

$1\le n\le 30$，$1\le C\le 2^{30}$，$1\le w_i\le 2^{30}$，$1\le a_i\le 500$。