E - Teamwork Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

かめくんとおむすびくんは、これから D 日間で N 個の仕事に取り組む予定です。仕事には順に 1, 2 \ldots N の番号が振られており、仕事 i の内容は以下のようなものです：

  • T_i = 1 のとき、かめくんが L_i 日目から R_i 日目に働く。報酬が 1 得られる。
  • T_i = 2 のとき、おむすびくんが L_i 日目から R_i 日目に働く。報酬が 1 得られる。
  • T_i = 3 のとき、かめくんとおむすびくんが共同で L_i 日目から R_i 日目に働く。報酬が V_i 得られる。

かめくんとおむすびくんは、N 個の仕事のいくつかを選び、取り組みます。このとき、仕事の種類にかかわらず、同じ人物が同じ日付に 2 つ以上の仕事に取り組むことは出来ないものとします。かめくんとおむすびくんが得られる報酬の和の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 10^9
  • T_i は 1,2,3 のいずれか(1 \leq i \leq N)
  • 1 \leq L_i \leq R_i \leq D (1 \leq i \leq N)
  • T_i = 3 のとき、1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 入力は全て整数

入力

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

N D
\mathrm{work}_1
\mathrm{work}_2
\vdots
\mathrm{work}_N

各 \mathrm{work}_i にはいくつかの整数が空白区切りで書かれており、その 1 つ目が T_i である。 \mathrm{work}_i は以下のいずれかの形式である。

1 L_i R_i

2 L_i R_i

3 L_i R_i V_i

出力

答えを出力せよ。

入力例 1

5 5
1 1 2
1 3 4
2 2 3
2 4 5
3 2 2 3

出力例 1

5

かめくんとおむすびくんは 2,4,5 番目の仕事を選ぶことで、条件を満たしつつ報酬 5 を達成することができます。 具体的には、 2,4,5 番目の仕事を行うと、かめくんは 2,3,4 日目に、おむすびくんは 2,4,5 日目に仕事が 1 つずつ入っている状態になります。