No.017 C

$1 \dots M$ の配列を用意して, $[0, l_i)$ と $(r_i, M]$ の区間にすべて $s_i$ を足す.

この結果, 配列の $k$ 番目の値は, $k$ 番目の宝石を取らなかったときにもらえる最大得点となる.

よって, 配列の最大値が答えとなる.

区間への足し込みはいもす法を使う.