| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 21 | 20 | 20 | 95.238% |
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번