問題文

いつも長ったらしくて癪に障るようなことばかり言っているSyntax君は、自分がモテない原因がこれであると確信しています。

そこで、砂糖をたくさん食べて舌を砂糖で包むことで、甘い言葉を囁くことができるようになると考えました。

長い研究の末、Syntax君は XX [g][\mathrm{g}] 以上の砂糖を食べることで甘い言葉を囁くことができるようになると突き止めました。

NN 種類の砂糖がそれぞれ 11 つずつ売っています。ii 種類目の砂糖は mim_i [g][\mathrm{g}]viv_i 円です

Syntax君が甘い言葉を囁くためには最低いくら必要ですか?

どうあがいても甘い言葉を囁くことができない場合は 1-1 を出力してください。

制約

  • 1N,X1031\leq N,X \leq 10^3
  • 1mi103 (1iN)1\leq m_i \leq 10^3\space (1\leq i \leq N)
  • 1vi104 (1iN)1 \leq v_i \leq 10^4\space (1\leq i \leq N)
  • 入力は全て整数

入力

N XN\space X\\ m1 v1m_1\space v_1\\ m2 v2m_2\space v_2\\ \ldots\\ mN vNm_N\space v_N\\

出力

答えを1行で出力してください。

サンプル

入力例1
3 10
7 4
3 3
4 2
出力例1
6

条件を満たす組み合わせのうち、

砂糖 11 と砂糖 22 の組み合わせでは7円、

砂糖 11 と砂糖 33 の組み合わせでは6円かかります。

最小であるのは6円です。


入力例2
3 10
4 5
3 3
2 4
出力例2
-1

どうあがいても甘い言葉を囁くことができません。

Submit


Go (1.21)