AT_pakencamp_2024_day3_1_e Teamwork

かめくんとおむすびくんは、これから $ 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 $ つ以上の仕事に取り組むことは出来ないものとします。かめくんとおむすびくんが得られる報酬の和の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

答えを出力せよ。

### Sample Explanation 1 かめくんとおむすびくんは $ 2,4,5 $ 番目の仕事を選ぶことで、条件を満たしつつ報酬 $ 5 $ を達成することができます。 具体的には、 $ 2,4,5 $ 番目の仕事を行うと、かめくんは $ 2,3,4 $ 日目に、おむすびくんは $ 2,4,5 $ 日目に仕事が $ 1 $ つずつ入っている状態になります。 ### Constraints - $ 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 $ ) - 入力は全て整数