速食店老闆為了獎勵員工，免費提供 $N$ 種配料給員工們做漢堡。老闆將所有配料排在桌上形成一列，員工必須沿著桌邊由左至右移動，經過配料時可以選擇不拿或拿取一份配料疊在現有漢堡的最上面。
小明希望能做出一份他認為最好吃的漢堡， 所謂好吃漢堡的定義如下
(1) 每一種配料 $i$ 小明 都會評分出美味程度 $S_i$ ，他拿到的所有配料總分越大越好
(2) 不能讓相同屬性的配料在堆疊時相鄰，不然會嚴重影響食物的美味程度。
舉例而言：
老闆準備 $N = 7$ 種配料排成由左至右依序一列編號為 $0$ ~ $6$。
小明給予配料的美味程度和屬性如下表所示。小明如果依序選擇編號 $0$、$1$、$4$ 和 $6$ 的配料 ，相同屬性的配料不會在堆疊時相鄰，而且可得 $2 + 7 + 4 + 9 = 22$ 分。
配料 $i$ 0 1 2 3 4 5 6
美味程度 $S_i$ 2 7 5 3 4 6 9
屬性 $W_i$ 1 2 2 1 1 3 3
請寫一個程式幫助小明計算他的漢堡的最高美味程度。
第一行有
兩 個 正整數 $N$ 和 $K$ 代表有 $N$ 種漢堡配料且配料共有 $K$ 種屬性。
第二行有 $N$ 個正整數 $S_0$ , $\dots$ , $S_{N - 1}$
兩兩之間以一個空白隔開， 表示這些漢堡配料的美味程度。
第三行有 $N$ 個整數 $W_0$ , $\dots$ , $W_{N - 1}$ 兩兩之間以一個空白隔開，表示這些漢堡配料的屬性。
$1 \leq N \leq 10^6$
$1 \leq K \leq 10^3$
$1 \leq S_i \leq 10^3$
$1 \leq W_i \leq K$
請輸出一個整數表示小明依照上述規則能得到的最高美味程度。
7 3 2 7 5 3 4 6 9 1 2 2 1 1 3 3
22
6 2 1 3 2 1 7 5 1 1 1 2 1 1
11
5 1 9 3 10 3 10 1 1 1 1 1
10
不公開 測資點#0 (10%): 1.0s , <10M
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1M
不公開 測資點#4 (10%): 1.0s , <1M
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <10M
不公開 測資點#7 (10%): 1.0s , <10M
不公開 測資點#8 (10%): 1.0s , <10M
不公開 測資點#9 (10%): 1.0s , <10M
第一組(10分)：$K = 1$
第二組(20分)：$N \leq 20$
第三組(30分)：$N \leq 10^3$
第四組(40分)：無特別限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 27993 |
|
g544 | 596 | 2021-11-08 17:05 | |
| 27952 |
|
g544 | 596 | 2021-11-06 21:31 |