| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 19 | 18 | 18 | 94.737% |
You just found a cave filled with $N$ treasures (numbered from 1ドル$ to $N$). Treasure $i$ has a weight of $W_i$ and a value of $V_i$.
Luckily, you also bring $M$ horse carts (numbered from 1ドル$ to $M$) to help you carry the treasures. Each cart can only carry one treasure; cart $j$ can only carry a treasure with weight at most $S_j$.
Determine the maximum total value of treasures that you can take using your horse carts.
The first line consists of two integers $N$ $M$ (1ドル ≤ N, M ≤ 100,円 000$).
Each of the next $N$ lines consists of two integers $W_i$ $V_i$ (1ドル ≤ W_i , V_i ≤ 10^6$).
The following line consists of $M$ integers $S_j$ (1ドル ≤ S_j ≤ 10^6$).
Output a single integer representing the maximum total value of treasures that you can take using your horse carts.
8 5 2 10 9 4 6 10 2 20 3 15 3 9 4 8 4 10 1 5 3 3 10
55
You can put treasures 8ドル,ドル 4ドル,ドル 5ドル$ and 3ドル$ to carts 2ドル,ドル 3ドル,ドル 4ドル,ドル and 5ドル,ドル respectively.
5 3 1 4 1 2 1 7 1 1 1 9 1 1 1
20
You can put treasures 1ドル,ドル 3ドル,ドル and 5ドル$ in any of your carts.
2 5 9 100 4 100 1 2 3 1 3
0
None of the treasures fit in any of your carts.
7 4 1 10 1 20 2 50 3 5 4 8 10 100 12 40 2 2 5 7
88
ICPC > Regionals > Asia Pacific > Indonesia > Indonesia National Contest > INC 2023 H번