串串手上有一個大背包，它的負重上限是 $W$ ，而他現在正想到一中街逛街。
街上商店總共有賣 $n$ 個商品和 $m$ 個魔法藥水，第 $i$ 個商品價值 $c_i$ 且重 $w_i$，第 $j$ 個藥水售價 $p_j$ ，且因為它很神奇，所以可以幫你的背包附載量增加，(不要問我為什麼可以)，可提高背包負重量 $x_j$ ，由於一中街人很多商品短缺，所以每種商品和魔法藥水都限購一次，串串想要知道怎麼買才可以賺到最多錢。
但串串已經迷失在血拼的世界裡面無法自拔，所以她想要詢問很電的你來幫忙規劃要買哪些東西。
輸入第一行有三個正整數 $n,\ m,\ W$ ，以空格隔開
接下來的 $n$ 行分別為第 $i$ 個商品的價值 $c_i$ 和重量 $w_i$ ，以空格隔開。
接下來的 $m$ 行分別為第 $j$ 個魔法藥水的價格 $p_j$ 和可提高背包負重的量 $x_j$ ，以空格隔開
$1 \leq n \leq 500$
$1 \leq m \leq 500$
$1 \leq W \leq 5000$
$1 \leq c_i,\ p_j \leq 10^9$
$0 \leq w_i,\ x_j \leq 500$
$\sum x_i \leq 5000$
輸出一個整數代表可以賺到的最大金額。
3 2 100 3 50 2 60 4 60 1 10 1 20
6
3 2 100 3 50 4 60 5 60 1 10 1 20
8
運算時可能會超過 32-bit 的正整數。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||