Manhattan Warp Machine 1

Time Limit : 1 sec, Memory Limit : 262144 KB

Problem C: Manhattan Warp Machine 1

Problem

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

Input

N x
d1 c1
...
dN cN

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

Constraints

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

  • 1 ≤ N ≤ 15
  • 0 ≤ x ≤ 105
  • 1 ≤ di ≤ 105
  • 1 ≤ ci ≤ 100
  • 与えられるマンハッタン距離diは全て異なる。

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