TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

90.0% (27/30)

Submission's AC Ratio

43.0% (58/135)

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

3 1
7122
3 1 0
4 2 0
5 3 0

Sample Output 1

12

Sample Input 2

5 1
700
900 1800 1
600 2700 1
800 2100 1
700 2400 1
600 3500 1

Sample Output 2

1000

Sample Input 3

7 8
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

43

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3
1 1000 524288 65536 1 2 3
2 1000 524288 65536 1 2 3
3 1000 524288 65536 1 2 3
4 1000 524288 65536 1 2 3
5 1000 524288 65536 2 3
6 1000 524288 65536 2 3
7 1000 524288 65536 2 3
8 1000 524288 65536 2 3
9 1000 524288 65536 2 3
10 1000 524288 65536 2 3
11 1000 524288 65536 2 3
12 1000 524288 65536 2 3
13 1000 524288 65536 2 3
14 1000 524288 65536 2 3
15 1000 524288 65536 3
16 1000 524288 65536 3
17 1000 524288 65536 3
18 1000 524288 65536 3
19 1000 524288 65536 3
20 1000 524288 65536 3
21 1000 524288 65536 3
22 1000 524288 65536 3
23 1000 524288 65536 3
24 1000 524288 65536 3
25 1000 524288 65536 3
26 1000 524288 65536 3
27 1000 524288 65536 3
28 1000 524288 65536 3
29 1000 524288 65536 3