AT_dp_w Intervals

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_w 長さ $ N $ の `0` と `1` からなる文字列を考えます。 この文字列のスコアを次のように計算します。 - 各 $ i $ ($ 1\ \leq\ i\ \leq\ M $) について、$ l_i $ 文字目から $ r_i $ 文字目までに `1` がひとつ以上含まれるならば、スコアに $ a_i $ を加算する。 文字列のスコアの最大値を求めてください。

N/A

N/A

### 制約 - 入力はすべて整数である。 - $ 1\ \leq\ N\ \leq\ 2\ ×\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 2\ ×\ 10^5 $ - $ 1\ \leq\ l_i\ \leq\ r_i\ \leq\ N $ - $ |a_i|\ \leq\ 10^9 $ ### Sample Explanation 1 `10001` のスコアは $ a_1\ +\ a_3\ =\ 10\ +\ 10\ =\ 20 $ となります。 ### Sample Explanation 2 `100` のスコアは $ a_1\ +\ a_2\ =\ 100\ +\ (-10)\ =\ 90 $ となります。 ### Sample Explanation 3 `0` のスコアは $ 0 $ となります。 ### Sample Explanation 4 答えは 32-bit 整数型に収まらない場合があります。 ### Sample Explanation 5 例えば、`101000` のスコアは $ a_2\ +\ a_3\ +\ a_4\ +\ a_5\ +\ a_7\ =\ 10\ +\ (-8)\ +\ 5\ +\ 9\ +\ (-6)\ =\ 10 $ となります。