În depozitul unei companii de construcţii se află N blocuri de piatră, de culoare albă sau neagră. Ele sunt aşezate în ordinea 1, 2, ..., N, de la intrarea în depozit către interior.
Blocurile de piatră trebuie să fie transportate pe un şantier de construcţii, în ordinea în care ele sunt depozitate, iar pentru aceasta va trebui închiriat un camion de la o companie de transport. Aceasta deţine Q tipuri de camioane. Camionul de tipul i (1 <= i <= Q) poate transporta maxim Ki blocuri de piatră la un moment dat şi pentru un transport se percepe taxa Ti.
Compania de transport este de parere că, pentru a-şi păstra clientela, trebuie să impună anumite standarde, indiferent de cât de absurde ar fi, deci impune condiţia ca toate blocurile de piatră plasate în camion la un transport să aibă aceeaşi culoare. Aşadar, pentru a fi transportate toate blocurile pe şantier, compania de construcţii va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi.
Pentru a micşora suma totală plătită, compania de construcţii are posibilitatea de a schimba culoarea oricărui bloc de piatră (din alb în negru sau din negru în alb); pentru fiecare bloc i (1 <= i <= N) se cunoaşte suma Si ce trebuie plătită de a-i schimba culoarea.
Cerinţă
Pentru fiecare dintre cele Q tipuri de camioane deţinute de compania de transport, determinaţi suma minimă pe care o va plăti compania de construcţii pentru a transporta toate cele N blocuri pe şantier.
Date de intrare
Fişierul de intrare trans.in conţine pe prima linie numărul întreg N, reprezentând numărul de blocuri de piatră din depozit. Pe fiecare dintre următoarele N linii se află informaţii referitoare la câte un bloc de piatra. Pe a i-a dintre aceste N linii se găsesc două numere întregi separate printr-un spaţiu: Ci Si, reprezentând culoarea celui de-al i-lea bloc (Ci este 0 pentru alb şi 1 pentru negru) şi respectiv suma ce trebuie plătită pentru a-i schimba culoarea (dacă este necesar). Pe următoarea linie se află numărul natural Q, reprezentând numărul de tipuri de camioane deţinute de compania de transport. Pe fiecare dintre următoarele Q linii se află informaţii referitoare la câte un camion. Pe cea de a i-a dintre aceste Q linii sunt scrise două numere naturale separate printr-un spaţiu Ki Ti, reprezentând numărul maxim de blocuri ce pot fi transportate simultan de către un camion de tipul i şi respectiv taxa ce trebuie plătită pentru fiecare transport efectuat.
Date de ieşire
Fişierul de ieşire trans.out va conţine Q linii. Pe cea de a i-a dintre aceste linii va fi afişată suma totală minimă plătită de compania de construcţii pentru a transporta toate cele N blocuri de piatră, în cazul în care ar închiria un camion de tipul i.
Restricţii
• 1 <= N <= 16000
• 1 <= Si <= 10000
• 1 <= Q <= 100
• 1 <= Ki <= N
• 1 <= Ti <= 100000
• Cel putin 40% dintre teste vor avea Q <= 10 şi Ki <= min(N, 100)