==Include(page="template/taskheader" task_id="trans")==
In depozitul unei companii de constructii se afla $N$ blocuri de piatra, de culoare alba sau neagra. Ele sunt asezate in ordinea $1$, $2$,.., $N$, de la intrarea in depozit catre interior. Blocurile de piatra trebuie sa fie transportate pe un santier de constructii, in ordinea in care ele sunt depozitate, iar pentru aceasta va trebui inchiriat un camion de la o companie de transport. Aceasta detine $Q$ tipuri de camioane. Camionul de tipul $i$ ({$1 ≤ i ≤ Q$}) poate transporta maxim $K{~i~}$ blocuri de piatra la un moment dat si pentru un transport se percepe taxa $T{~i~}$.
Compania de transport este de parere ca, pentru a-si pastra clientela, trebuie sa impuna anumite standarde, indiferent de cat de absurde ar fi, deci impune conditia ca toate blocurile de piatra plasate in camion la un transport sa aiba aceeasi culoare. Asadar, pentru a fi transportate toate blocurile pe santier, compania de constructii va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi. Pentru a micsora suma totala platita, compania de constructii are posibilitatea de a schimba culoarea oricarui bloc de piatra (din alb in negru sau din negru in alb); pentru fiecare bloc $i$ ({$1 ≤ i ≤ N$}) se cunoaste suma $S{~i~}$ ce trebuie platita pentru a-i schimba culoarea.
h2. Cerinta
Pentru fiecare dintre cele $Q$ tipuri de camioane detinute de compania de transport, determinati suma minima pe care o va plati compania de constructii pentru a transporta toate cele $N$ blocuri pe santier.
h2. Date de intrare
Fisierul de intrare $trans.in$ contine pe prima linie numarul intreg $N$, reprezentand numarul de blocuri de piatra din depozit. Pe fiecare dintre urmatoarele $N$ linii se afla informatii referitoare la cate un bloc de piatra. Pe a $i$-a dintre aceste $N$ linii se gasesc doua numere intregi separate printr-un spatiu: {$C{~i~} S{~i~}$}, reprezentand culoarea celui de-al $i$-lea bloc ({$C{~i~}$} este 0 pentru alb si 1 pentru negru) si respectiv suma ce trebuie platita pentru a-i schimba culoarea (daca este necesar). Pe urmatoarea linie se afla numarul natural $Q$, reprezentand numarul de tipuri de camioane detinute de compania de transport. Pe fiecare dintre urmatoarele $Q$ linii se afla informatii referitoare la cate un camion. Pe cea de a $i$-a dintre aceste $Q$ linii sunt scrise doua numere naturale separate printr-un spatiu {$K{~i~} T{~i~}$}, reprezentand numarul maxim de blocuri ce pot fi transportate simultan de catre un camion de tipul $i$ si respectiv taxa ce trebuie platita pentru fiecare transport efectuat.
h2. Date de iesire
Fisierul de iesire $trans.out$ va contine $Q$ linii. Pe cea de a $i$-a dintre aceste linii va fi afisata suma totala minima platita de compania de constructii pentru a transporta toate cele $N$ blocuri de piatra, in cazul in care ar inchiria un camion de tipul $i$.
h2. Restrictii si precizari
* $1 ≤ N ≤ 16 000$
* $1 ≤ S{~i~} ≤ 10 000$
* $1 ≤ Q ≤ 100$
* $1 ≤ K{~i~} ≤ N$
* $1 ≤ T{~i~} ≤ 100 000$
h2. Exemplu
table(example). |_. trans.in|_. trans.out|
|4
0 2
1 3
0 10
1 2
3
4 1000
4 1
2 5
|1005
4
14|
==Include(page="template/taskfooter" task_id="trans")==
==Include(page="template/taskheader" task_id="trans")==
==Include(page="template/raw")==
trans
In depozitul unei companii de constructii se afla N blocuri de piatra, de culoare alba sau neagra. Ele sunt asezate in ordinea 1,2,..,N, de la intrarea in depozit catre interior. Blocurile de piatra trebuie sa fie transportate pe un santier de constructii, in ordinea in care ele sunt depozitate, iar pentru aceasta va trebui inchiriat un camion de la o companie de transport. Aceasta detine Q tipuri de camioane. Camionul de tipul i (1 <= i <= Q) poate transporta maxim K[i] blocuri de piatra la un moment dat si pentru un transport se percepe taxa T[i].
Compania de transport este de parere ca, pentru a-si pastra clientela, trebuie sa impuna anumite standarde, indiferent de cat de absurde ar fi, deci impune conditia ca toate blocurile de piatra plasate in camion la un transport sa aiba aceeasi culoare. Asadar, pentru a fi transportate toate blocurile pe santier, compania de constructii va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi. Pentru a micsora suma totala platita, compania de constructii are posibilitatea de a schimba culoarea oricarui bloc de piatra (din alb in negru sau din negru in alb); pentru fiecare bloc i (1 <= i <= N) se cunoaste suma S[i] ce trebuie platita de a-i schimba culoarea.
h2. Cerinta
Pentru fiecare dintre cele Q tipuri de camioane detinute de compania de transport, determinati suma minima pe care o va plati compania de constructii pentru a transporta toate cele N blocuri pe santier.
h2. Date de Intrare
Fisierul de intrare trans.in contine pe prima linie numarul intreg N, reprezentand numarul de blocuri de piatra din depozit. Pe fiecare dintre urmatoarele N linii se afla informatii referitoare la cate un bloc de piatra. Pe a i-a dintre aceste N linii se gasesc doua numere intregi separate printr-un spatiu: C[i] S[i], reprezentand culoarea celui de-al i-lea bloc (C[i] este 0 pentru alb si 1 pentru negru) si respectiv suma ce trebuie platita pentru a-i schimba culoarea (daca este necesar). Pe urmatoarea linie se afla numarul natural Q, reprezentand numarul de tipuri de camioane detinute de compania de transport. Pe fiecare dintre urmatoarele Q linii se afla informatii referitoare la cate un camion. Pe cea de a i-a dintre aceste Q linii sunt scrise doua numere naturale separate printr-un spatiu K[i] T[i], reprezentand numarul maxim de blocuri ce pot fi transportate simultan de catre un camion de tipul i si respectiv taxa ce trebuie platita pentru fiecare transport efectuat.
h2. Date de Iesire
Fisierul de iesire trans.out va contine Q linii. Pe cea de a i-a dintre aceste linii va fi afisata suma totala minima platita de compania de constructii pentru a transporta toate cele N blocuri de piatra, in cazul in care ar inchiria un camion de tipul i.
h2. Restrictii si precizari
. 1 <= N <= 16.000
. 1 <= S[i] <= 10.000
. 1 <= Q <= 100
. 1 <= K[i] <= N
. 1 <= T[i] <= 100.000
h2. Exemplu
|trans.in |trans.out |
|4 |1005 |
| | |
|0 2 |4 |
| | |
|1 3 |14 |
| | |
|0 10 | |
| | |
|1 2 | |
| | |
|3 | |
| | |
|4 1000 | |
| | |
|4 1 | |
| | |
|2 5 | |
==Include(page="template/taskfooter" task_id="trans")==
