0 Judge
Code: 0
(雖然同名,不過這個故事跟名偵探柯南中的基德並沒有關係)
怪盜基德,所有無良商人的惡夢,他經常神不知鬼不覺「光顧」各種黑心商人的商店,並暗中將竊取的財物贈予需要幫助的人們。
最近基德盯上了一家剝削童工開採寶石的珠寶供應商。就在今天,他成功地潛入了對方的珠寶倉庫。
潛入了珠寶倉庫後,基德發現倉庫內的珠寶總共有$N$顆,每顆珠寶依照色澤及品質定有自己的價格。
此外,這些經過加工打磨的珠寶們被依重量分成$K$類,第$i$類的珠寶重量皆為$w_i$。
由於倉庫的規模實在太大,基德的袋子沒辦法裝下所有的珠寶,因此他必須想辦法在袋子能夠容納的前提下,最大化自己能帶走的珠寶價格。
更明確地說,基德的袋子能承受至多$W$的重量,他必須選出一個珠寶的子集合,使得這些珠寶總重量$ \leq W$,並且總價格越高越好。
這讓基德傷透了腦筋,他需要一筆鉅款來接濟他窮困的同班同學,你能幫幫基德算出這一次他最多可以盜得多少價值的珠寶嗎?
本題目中,一個檔案只會有一筆測資。
第一行有三個整數,分別為$N$、$W$和$K$。
第二行包含$K$個整數,第$i$個整數代表$w_i$,即第$i$類珠寶的重量。
接下來有$N$行,第$j$行有兩個整數$p_j$、$t_j$,代表第$j$顆珠寶的價值,以及它所屬的種類。
輸出一行,代表負重$W$的袋子最多可以裝下多少價值的珠寶。
$1 \leq N, W \leq 10^5$
$1 \leq K \leq 20$
$1 \leq w_i \leq W$
$1 \leq p_j \leq 10^3$
$1 \leq t_j \leq K$
額外限制 $1 \leq W \leq 10^3$
額外限制 $1 \leq N \leq 10^3$
5 10 6
1 4 7 2 5 2
5 1
2 2
10 3
4 4
6 6
21
6 3 1
1
8 1
1 1
6 1
7 1
11 1
7 1
26
9 20 3
1 4 3
3 1
4 1
2 1
12 2
16 2
6 2
9 3
12 3
6 3
64
偷竊在臺灣其實是違法行為,根據我國刑法第320條,
意圖為自己或第三人不法之所有,而竊取他人之動產者,為竊盜罪,處五年以下有期徒刑、拘役或五百元以下罰金。
意圖為自己或第三人不法之利益,而竊佔他人之不動產者,依前項之規定處斷。
前二項之未遂犯罰之。
可看出基德所作所為事實上屬於違法行為,此故事純屬虛構,請勿模仿。