D - タクシー

Contest Duration: 2015-01-24 20:00:00+0900 - 2015-01-24 22:00:00+0900 (local time) (120 minutes)

D - タクシー Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

ある星で、プログラミングコンテスト「ドワンゴからの挑戦状」の予選が行われ、予選通過者を本選会場へと招待することになりました。

この星には長さ L の環状線 1 本があり、環状線上に N 個の都市があります。都市には 1 から N までの番号が、都市 1 を基準として時計回りに昇順に付けられています。

本選は 1 つ以上の都市で行われ、各会場ごとに生放送をすることになりました。

各都市と各会場ごとに、その都市に住んでいる本選出場者数と会場に入る本選出場者数は決まっています。

会場に入る本選出場者数の合計は本選出場者数の合計とぴったり一致しています。

都市によっては、その都市に住んでいる本選出場者数と会場に入る本選出場者数が一致していないこともあり、その場合は都市間で本選出場者をタクシーで移動させる必要があります。

タクシーは環状線上を移動し、本選出場者 1 人ごとに移動距離に等しいコストが掛かります。

移動にかかるコストの合計値として考えられる最小値を求めるプログラムを作成してください。

入力は以下の形式で標準入力から与えられる。

N L
a_1 b_1 c_1
a_2 b_2 c_2
:
a_N b_N c_N

1 行目には、都市の個数 N (2 ≦ N ≦ 100,000) と環状線の長さ L (N ≦ L ≦ 10,000,000) が空白区切りで与えられる。
2 行目から N 行には、各都市に関する情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には 3 つの整数 a_i (0 ≦ a_i ≦ L - 1), b_i (0 ≦ b_i ≦ 100,000), c_i (0 ≦ c_i ≦ 100,000) が空白区切りで与えられる。これは、都市 i が環状線上を都市 1 を基準として時計回りに a_i だけ進んだところにあり、都市 i から出る本選出場者数が b_i 人で、c_i = 0 なら都市 i には会場はなく、c_i ＞ 0 なら都市 i には本選出場者を c_i 人招待することを表す。
a_1 = 0 であり、すべての整数 i (2 ≦ i ≦ N) に対して a_i ＞ a_{i-1} が成り立つ。
b_1 + ... + b_N = c_1 + ... + c_N である。
b_1 + ... + b_N ≧ 1 である。

この問題には部分点が設定されています。

N ≦ 5,000 および b_1 + ... + b_N ≦ 5,000 を満たすデータセット 1 にすべて正解すると、15 点が得られます。
N ≦ 5,000 を満たすデータセット 2 にすべて正解すると、上記に加えてさらに 30 点が得られます。
追加制約のないデータセット 3 にすべて正解すると、上記に 2 つに加えてさらに 55 点が得られ、全体で 100 点が得られます。

移動コストの合計値として考えられる最小値を 1 行に出力せよ。出力の末尾にも改行を入れること。

以下のような移動を考えます。

この移動の結果、移動後のどの都市についても、会場があるならその会場に入る人数とその都市にいる本選出場者数が等しく、かつどの本選出場者も会場に入れます。

移動コストの合計値は 4 + 2 + 6 = 12 で、この値が最小値となります。