g6-07940. 开心的礼物 未做

小杨想给班里同学买礼物。商店里有 $n$ 件礼物，第 $i$ 件价格 $w_i$ 元、重要度 $k_i$。他手里一共有 $V$ 元，每件礼物至多买一件，总价不能超过 $V$。一件礼物的快乐值定义为价格与重要度的乘积 $w_i\times k_i$，求他能获得的最大快乐值总和。

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

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

一行一个整数，表示最大快乐值总和。

输入 1

3 6
2 3
3 4
4 5

输出 1

26

买第 1、3 件：花费 $2+4=6$，快乐值 $2\times 3+4\times 5=26$。

$1\le n\le 25$，$1\le V\le 3\times 10^4$，$1\le w_i,k_i\le 100$。