Problem C: Manhattan Warp Machine 1

Problem

とある宇宙では、1次元の整数座標点上に星が存在し、宇宙人達はマンハッタンワープ装置を使い、星間を移動している。
このワープ装置には、N個のボタンが付いており、ボタンiを押すと、現在いる星からのマンハッタン距離がd_iである任意の星にコストc_iでワープすることができる。
今、点0の星にいるある宇宙人が点xの星に行きたいと考えている。
点xの星に辿り着くまでの最小のコストを答えよ。
辿り着けない場合は-1を出力せよ。
1次元上の整数座標点には必ず星が存在する。
点x₁と点x₂間のマンハッタン距離は| x₁ - x₂ |で表される。

Input

N x
d1 c1
...
dN cN

入力は全て整数で与えられる。
1行目にNと行きたい星の座標xが空白区切りで与えられる。
続くN行に、移動可能なマンハッタン距離d_iとコストc_iが1行ずつ空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• 1 ≤ N ≤ 15
• 0 ≤ x ≤ 10⁵
• 1 ≤ d_i ≤ 10⁵
• 1 ≤ c_i ≤ 100
• 与えられるマンハッタン距離d_iは全て異なる。

Output

点xの星に辿り着くまでにかかる最小コストを1行に出力せよ。辿り着くことが不可能な場合は-1を出力せよ。

Sample Input 1

2 5
1 1
2 1

Sample Output 1

3

Sample Input 2

2 12
9 1
3 2

Sample Output 2

3

Sample Input 3

1 3
4 1

Sample Output 3

-1