005 - Hちゃんのおつかい

問題

某有名動画配信者のHちゃんはおつかいに来た。

このお店には n 個の商品があり、それらにはそれぞれ基本価値 v_i と重さ w_i がある。

ここで注意すべきことがある。それは、物の重さが重いほどその物の価値が高くなるということだ。具体的には、物の価値 p_i は物の重さ w_i のその物の基本価値 v_i 乗となる。
(p_i = w_i ^ v_i)

Hちゃんはそこまで力持ちなわけではない。よって、買った物の重さの総和が W を超えると「ふにー！」となり持ち運びができなくなるため、困ってしまう。

そこでHちゃんは重さが W を超えないで、かつ、買う商品の価値が最大になるように買い物をしようと考えた。

さらに、この国では特殊なルールがある。それは大きくなりすぎたひとつの物の価値は1000000007(10⁹+7)で割ったあまりとするというものだ。

あなたは重さの総和が W を超えないで、かつ、買う商品の価値が最大になるような、価値の総和を求めて、Hちゃんの買い物の手伝いをしようと考えた。

また、Hちゃんのおこずかいは充分にある。

(最終的な出力結果は10⁹+7で割った余りでなくていいです。)

入力

n W
v0 w0
・
・
・
vn-1 wn-1

１行目には商品の数 n とHちゃんが持てる物の重さの総和 Wが与えられる。

２行目から続く n 行に商品の基本価値 v_i と重さ w_i が与えられる。

また、全ての商品において、在庫は１つずつしかないとする。

出力

重さの総和が W を超えないで、かつ、商品の価値が最大になるように買う商品を選んだときの商品の価値の総和を出力せよ。

制約

全ての入出力ケースにおいて以下を満たす。

• 1 ≦ n ≦ 100
• 1 ≦ W ≦ 10⁴
• 1 ≦ v_i ≦ 10⁹
• 1 ≦ w_i ≦ 10⁴

入出力例

入力例

5 10
4 5
5 4
1 2
3 1
8 9

出力例

43046722

解説

5 ^ 4 = 625
4 ^ 5 = 1024
2 ^ 1 = 2
1 ^ 3 = 1
9 ^ 8 = 43046721
となり、この中で合計の重さを10以下で価値を最大にするには、4つ目の商品と5つ目の商品を買った時である。
この場合、重さは10になり、価値の総和は43046722となる。