2177 . 這是抄襲的問題
TopCoder
Tags
Description
今天ZCK想要出練習賽，但是他不想要抄襲別人的題目
所以雖然他每天都會看到各種毒又毒的題目，他並不會隨便拿來毒別人
他想辦法生出了一些題目，這些題目分別有一些(大家評估的)優質度還有難度(難度都相異)
不過，有些題目是自己想到的，有些題目是從別的OJ抓來的(會告訴你每個題目是自己想到的還是從某個編號的OJ抓的)
因為是練習賽，他希望題目可以照難度排序
他希望選一組題目，難度遞增並且總優質度越高越好
但是，他不太希望參賽者看到題目都從同一個OJ上抄來，不然很容易被抓包然後罵翻
ZCK所看到的題目總共有$N$個，然後這些題目都是從$M$個OJ裡頭抓出來的或者是自己出的。
因此ZCK將選出，假設選出了$K$個題目$P_1, P_2,\dots,P_K$，那麼對於$1\leq i<K$，如果$P_i,P_{i+1}$的來源是同一個OJ的話，總優質度就得扣掉一次該OJ的知名度
以上的條件有一個特例，也就是如果題目是ZCK自己出的話，那就不必扣掉知名度（因為ZCK是無限知名的）
（就算是同一個OJ，在很多位置出現的話當然得扣掉那麼多次）
也就是說，一組題目的總優質度是「所有題目的優質度的總和」扣掉「所有相鄰的題目且來源是同一個OJ的OJ知名度」
Input Format
第一行有一個正整數$N,M$表示總共有$N$道題目，還有$M$種OJ
第二行有$M$個用空白隔開的非負整數，第$i$個數字$A_i$表示第$i$種OJ的知名度
接下來$N$行，每行有三個數字$Q, D, X$，分別代表該題的優質度、難度跟是從什麼編號的OJ抓的。如果$X=0$代表那是ZCK自己產出的題目，不用擔心跟相鄰的題目撞OJ
有些題目實在太毒了，或是水到不是題目，因此有些題目的優質度可能小於零
$N,M \leq 5000$
$0 \leq A_i \leq 10^ 9$
$-10^ 9 \leq Q \leq 10^ 9$
$0 \leq D \leq 10000$
$0 \leq X \leq M$
Output Format
請輸出一行整數表示最佳的總優質度
注意你可以不選任何題目，所以答案不會是負的
Sample Input 1
7122
3 1 0
4 2 0
5 3 0
Sample Output 1
Sample Input 2
700
900 1800 1
600 2700 1
800 2100 1
700 2400 1
600 3500 1
Sample Output 2
Sample Input 3
5 7 5 9 5 1 4 3
10 1300 0
10 600 1
4 1100 0
2 2300 1
10 2000 1
0 1700 8
9 1800 7
Sample Output 3
Hints
JOJO，這是我最後的波紋了！
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | $N\leq 10$，難度分別依序是$1,2,\cdots,N$，並且所有$X$都是$0$ | 10 |
| 2 | 0~14 | $N \leq 10$ | 20 |
| 3 | 0~29 | 無其他限制 | 70 |