Nice-Hotel

Time limit: 0.35s Memory limit: 12MB Input: hotel.in Output: hotel.out

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 FF lei, construirea unui etaj EE lei (parterul se consideră și el etaj), iar construirea unei camere CC lei. De asemenea, el știe că pe un etaj, nu pot exista mai mult de KK camere.

Vestea noului hotel circulă repede prin oraș, așa de repede, încât Constănţeanu' a primit NN oferte de rezervare, de dinainte să înceapă construcția. Pentru oferta cu numărul de ordine i, i{1,,N}i, \ i \in \{ 1, \ldots ,N\} se cunosc TiT_i, numărul de camere rezervate și ViV_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 TiT_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 44 numere, în această ordine și separate prin câte un spațiu: F,E,C,KF, E, C, K.
Pe a doua linie se va găsi numărul NN de rezervări primite.
Pe următoarele NN linii se vor găsi câte 22 numere, TiT_i și ViV_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 22 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

  • 1N,Ti1 000 0001 \leq N, T_i \leq 1 \ 000 \ 000;
  • 0F,E,C,Vi1 000 000 0000 \leq F, E, C, V_i \leq 1 \ 000 \ 000 \ 000;
  • 1K1 000 000 0001 \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.
# Punctaj Restricţii
1 30 N,F,E,C,K,Vi,Ti1 000N, F, E, C, K, V_i, T_i \leq 1 \ 000
2 20 N,Ti1 000N, T_i \leq 1 \ 000
3 20 F,E=0F, E=0
4 30 Fără restricții suplimentare

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 55 camere este 50+20+105=12050+20+10 \cdot 5 = 120 lei (se construiește fundația, parterul și 55 camere).
Încasările unui hotel de 55 camere sunt 90+40=13090+40=130 lei (se va putea accepta doar oferta de 55 și oferta de 33 camere).
Profitul acesta este maxim.

Log in or sign up to be able to send submissions!