町 \(i\) とその町に辿り着くまでにかかった費用 \(j\) を用いて \((i, j)\) を頂点するグラフを考える. そして \((S_i, k) \rightarrow (T_i, k+Y_i)\) となる辺を張る.

あとは Dijkstra 法を使って \((0, 0)\) から \((N, x) \ (1 \leq x \leq C)\) までの最短距離を求め, その最小値を計算する.