AT_dwango2015_prelims_4 タクシー

[problemUrl]: https://atcoder.jp/contests/dwango2015-prelims/tasks/dwango2015_prelims_4 ある星で、プログラミングコンテスト「ドワンゴからの挑戦状」の予選が行われ、予選通過者を本選会場へと招待することになりました。 この星には長さ $ 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 $ である。

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

### 部分点 この問題には部分点が設定されています。 - $ N\ ≦\ 5,000 $ および $ b_1\ +\ ...\ +\ b_N\ ≦\ 5,000 $ を満たすデータセット $ 1 $ にすべて正解すると、$ 15 $ 点が得られます。 - $ N\ ≦\ 5,000 $ を満たすデータセット $ 2 $ にすべて正解すると、上記に加えてさらに $ 30 $ 点が得られます。 - 追加制約のないデータセット $ 3 $ にすべて正解すると、上記に $ 2 $ つに加えてさらに $ 55 $ 点が得られ、全体で $ 100 $ 点が得られます。 ### Sample Explanation 1 以下のような移動を考えます。 - 都市 $ 3 $ の本選出場者 $ 1 $ 人が都市 $ 1 $ にタクシーで反時計回りに移動する。移動コストは $ 4\ ×\ 1\ =\ 4 $ である。 - 都市 $ 6 $ の本選出場者 $ 1 $ 人が都市 $ 4 $ にタクシーで反時計回りに移動する。移動コストは $ 2\ ×\ 1\ =\ 2 $ である。 - 都市 $ 7 $ の本選出場者 $ 2 $ 人が都市 $ 1 $ にタクシーで時計回りに移動する。移動コストは $ 2 $ 人あわせて $ 3\ ×\ 2\ =\ 6 $ である。 この移動の結果、移動後のどの都市についても、会場があるならその会場に入る人数とその都市にいる本選出場者数が等しく、かつどの本選出場者も会場に入れます。 移動コストの合計値は $ 4\ +\ 2\ +\ 6\ =\ 12 $ で、この値が最小値となります。