とある宇宙では、1次元の整数座標点上に星が存在し、宇宙人達はマンハッタンワープ装置を使い、星間を移動している。
このワープ装置には、N個のボタンが付いており、ボタンiを押すと、現在いる星からのマンハッタン距離がdiである任意の星にコストciでワープすることができる。
今、点0の星にいるある宇宙人が点xの星に行きたいと考えている。
点xの星に辿り着くまでの最小のコストを答えよ。
辿り着けない場合は-1を出力せよ。
1次元上の整数座標点には必ず星が存在する。
点x1と点x2間のマンハッタン距離は| x1 - x2 |で表される。
N x d1 c1 ... dN cN
入力は全て整数で与えられる。
1行目にNと行きたい星の座標xが空白区切りで与えられる。
続くN行に、移動可能なマンハッタン距離diとコストciが1行ずつ空白区切りで与えられる。
入力は以下の条件を満たす。
点xの星に辿り着くまでにかかる最小コストを1行に出力せよ。辿り着くことが不可能な場合は-1を出力せよ。
2 5 1 1 2 1
3
2 12 9 1 3 2
3
1 3 4 1
-1