Mirror - Future for Future IX - 2024 | Nice-Hotel

Iarna, hotelurile din Bansko au mare succes. Atât de mare este profitul lor, încât Constănţeanu' s-a gândit să construiască și el unul. Provocarea este destul de mare, deoarece el știe că fundația hotelului va costa $F$ lei, construirea unui etaj $E$ lei (parterul se consideră și el etaj), iar construirea unei camere $C$ lei. De asemenea, el știe că pe un etaj, nu pot exista mai mult de $K$ camere.

Vestea noului hotel circulă repede prin oraș, așa de repede, încât Constănţeanu' a primit $N$ oferte de rezervare, de dinainte să înceapă construcția. Pentru oferta cu numărul de ordine $i, \ i \in \{ 1, \ldots ,N\}$ se cunosc $T_i$, numărul de camere rezervate și $V_i$, suma pe care clienţii sunt dispuși să o plătească pentru cazare. O singură problemă are Constănţeanu', și anume că dacă hotelul lui are mai puțin de $T_i$ camere, atunci el va pierde toată rezervarea și nu va primi niciun ban.

Cerință

Constănţeanu' dorește să cunoască profitul maxim (diferența dintre suma de bani folosită pentru a construi hotelul și suma de bani încasată din rezervări maximă) și numărul minim de camere ce obțin profitul maxim (deoarece acesta nu dorește să muncească mai mult decât trebuie).

Date de intrare

Pe prima linie a fișierului de intrare hotel.in se vor găsi $4$ numere, în această ordine și separate prin câte un spațiu: $F, E, C, K$.
Pe a doua linie se va găsi numărul $N$ de rezervări primite.
Pe următoarele $N$ linii se vor găsi câte $2$ numere, $T_i$ și $V_i$, separate printr-un spațiu.

Date de ieșire

Se va afișa o singură linie în fișierul de ieșire hotel.out, care va conține $2$ numere separate prin spațiu. Primul va fi profitul maxim, iar al doilea numărul minim de camere ce trebuie construite pentru a atinge acest profit.

Restricții și precizări

• $1 \leq N, T_i \leq 1 \ 000 \ 000$;
• $0 \leq F, E, C, V_i \leq 1 \ 000 \ 000 \ 000$;
• $1 \leq K \leq 1 \ 000 \ 000 \ 000$;
• Profitul maxim poate fi negativ (afacerea lu' Constănţeanu' nu va avea un viitor prea fericit);
• Constănțeanu' este foarte determinat, el va construi minim o cameră;
• Deși unele dintre ofertele primite au fost scrise în scop de ironie (acestea necesitând un număr de camere de ordinul miilor sau chiar milioanelor), Constănţeanu' va lua fiecare ofertă în serios.

Exemplu

hotel.in

50 20 10 5
4
5 90
3 40
7 10
10 30

hotel.out

10 5

Explicație

Costul construirii unui hotel de $5$ camere este $50+20+10 \cdot 5 = 120$ lei (se construiește fundația, parterul și $5$ camere).
Încasările unui hotel de $5$ camere sunt $90+40=130$ lei (se va putea accepta doar oferta de $5$ și oferta de $3$ camere).
Profitul acesta este maxim.