問題
あなたは, 2 箇所のコンサートホールを運営することになりました.
xi 日から yi 日までの期間を料金 wi を使用したいというコンサートの申し出が N 件きています.
2 箇所のコンサートホールに上手くコンサートを割り当てたとき, 料金の和の最大値を求めてください. 割り当てないコンサートがあっても構いません. ただし, それぞれのホールでコンサートの日程が被らないようにする必要があります.
入力
N x1 y1 w1 x2 y2 w2 : xN yN wN
- 1 行目に申し出の件数 N(1 ≤ N ≤ 1 000) が与えられる.
- 2 行目から N 行にかけて申し出の情報が与えられる. それぞれ xi 日から yi 日までの期間を料金 wi で使用することをあらわす. (1 ≤ xi ≤ yi ≤ 365, 1 ≤ wi ≤ 10 000)
出力
2 箇所のコンサート会場にコンサートを上手く割り当てたときの料金の和の最大値を 1 行に出力せよ.
入出力例
入力例 1
4 1 2 10 2 3 10 3 3 10 1 3 10
出力例 1
30
たとえば, 以下のように選ぶとき料金は最大となる.
- 会場 1: 1 番目と 3 番目
- 会場 2: 2 番目
入力例 2
6 1 20 1000 3 25 10000 5 15 5000 22 300 5500 10 295 9000 7 7 6000
出力例 2
25500
入力例 3
8 32 251 2261 123 281 1339 211 235 5641 162 217 7273 22 139 7851 194 198 9190 119 274 878 122 173 8640
入力例 3
38595