Problem G
Löjtnant Slotto
Languages
en
sv
Löjtnant Slotto befäster just nu $N$ stycken slott. Varje slott innehåller rikedomar värda $l_i$ guldmynt och försvaras av $g_i$ soldater.
Du planerar att anfalla Slottos slott och har totalt $T$ trupper till ditt förfogande. Varje trupp kan skickas för att anfalla exakt ett slott. Om du anfaller slott $i$ med minst $g_i$ soldater lyckas anfallet, och du kan då plundra dess rikedomaer. Om du skickar färre soldater kommer anfallet att misslyckas.
Om du fördelar dina trupper optimalt, hur många guldmynt värt av rikedomar kan du få?
Indata
Den första raden av indata innehåller heltalen $N$ och $T$ ($1 \leq N \leq 2 \cdot 10^5$, $1 \leq T \leq 10^6$), antalet slott det finns och antalet trupper du har.
De följande $N$ raderna beskriver vardera ett slott. Varje av dessa rader innehåller heltalen $l_i$ och $g_i$ ($1 \leq l_i \leq 5$, $1 \leq g_i \leq 10^6$), värdet av rikedomarna i slott $i$ och antalet vaktar som vaktar slott $i$.
Utdata
Skriv ut ett heltal: största mängden rikedomar du kan erövra om du fördelar dina trupper optimalt.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$7$ |
$l_i=1$ |
|
$2$ |
$12$ |
$N, T \leq 500$ |
|
$3$ |
$24$ |
$N \leq 5000$ |
|
$4$ |
$17$ |
$l_i \leq 2$ |
|
$5$ |
$40$ |
Inga ytterligare begränsningar. |
Förklaring av exempelfall
I Exempelfall $1$ är en optimal lösning att skicka $5$ trupper till slott $2$ (den med $l_i=g_i=4$) och $2$ trupper till slott $4$ (den med $l_i=g_i=2$), och du får då sammanlagt $6$ guldmynt värt av rikedomar.
I exempelfall $2$ är en optimal lösning att skicka alla trupper till slott $1$.
I båda fallen finns det andra fördelningar som ger lika mycket rikedomar.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 7 5 6 4 4 3 5 2 2 1 3 |
6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 10 5 9 3 6 3 6 |
5 |
