Matcha

Ștefan este un freelancer celebru și obișnuiește să poarte quarter zip și să bea matcha pe Primăverii. Acesta a comandat $N$ matcha-uri diferite. Fiecare matcha are un nivel de cofeină, $c_i$, și un nivel de fericire, $f_i$, pe care Ștefan îl acumulează în momentul în care îl bea. Ștefan, fiind un mare fan matcha, își dorește să bea cât mai multe băuturi, însă, fiindcă este o persoană responsabilă și este foarte atent la programul lui de somn, nu-și dorește să își perturbe somnul din cauza cantității de cofeină. El știe că dacă va bea o cantitate de cofeină cel mult egală cu $C$, atunci va avea un somn sănătos și odihnitor.
Fix înainte de a începe să se delecteze cu băuturile lui, Ștefan este întâmpinat de Costel, care îi face cadou prietenului său încă o cană cu matcha, cu un nivel $a$ de fericire și $b$ de cofeină.

Cerință

Se dau $Q$ situații diferite pentru băutura adusă cadou de către Costel.
Ștefan vă roagă să aflați care este nivelul maxim de fericire pe care îl poate atinge, în fiecare dintre cele $Q$ situații, astfel încât să poată dormi liniștit la noapte. Se știe faptul că Ștefan nu este nevoit să termine toate cănile începute, ci poate să bea doar o parte din cantitatea de matcha. Fericirea adusă de o fracțiune de matcha este direct proporțională cu nivelul de cofeină al acesteia.

Date de intrare

Pe prima linie a fișierului de intrare matcha.in se găsesc trei numere naturale, $N$, $C$ și $Q$ cu semnificațiile din enunț.
Pe a doua linie se vor găsi $N$ numere naturale, reprezentând nivelul de fericire $f_i$ al fiecărei băuturi.
Pe cea de-a treia linie se vor găsi $N$ numere naturale, reprezentând nivelul de cofeină $c_i$ al fiecărei băuturi.
Pe următoarele $Q$ linii se vor găsi câte două numere naturale, $a_i$ și $b_i$, reprezentând nivelul de fericire și de cofeină al băuturii aduse de Costel.

Date de ieșire

În fișierul de ieșire matcha.out se vor găsi $Q$ linii, fiecare conținând un singur număr rațional, reprezentând răspunsul pentru fiecare dintre cele $Q$ situații. Răspunsul afișat va fi considerat corect dacă diferența absolută dintre el și răspunsul real este mai mică sau egală decât $10^{−4}$.

Restricții și precizări

• $1 \leq N, Q \leq 100 \ 000$;
• $1 \leq C \leq 1 \ 000 \ 000 \ 000$;
• $1 \leq c_i, f_i, a_i, b_i \leq 1 \ 000 \ 000 \ 000$;

  #	Punctaj	Restricții
  1	13	$b_i > C$ și $N, Q \leq 1 \ 000$
  2	9	$b_i > C$
  3	11	$c_i = b_i = 1$ și $N, Q \leq 1 \ 000$
  4	7	$c_i = b_i = 1$
  5	29	$N, Q \leq 1 \ 000$
  6	31	Fără restricții suplimentare

Exemplul 1

matcha.in

3 10 2
10 15 20
2 5 4
12 3
36 6

matcha.out

45
56

Exemplul 2

matcha.in

2 7 2
10 5
4 2
6 3
12 4

matcha.out

17
19.5

Explicație

Băuturile inițiale deținute de Ștefan:
B1: fericire $10$, cofeină $4$
B2: fericire $5$, cofeină $2$
Capacitatea maximă de cofeină pentru a dormi bine este $C = 7$.

Pentru prima situație ($Q = 1$):
Costel aduce o băutură cu fericire $6$ și cofeină $3$.
Bea toată B1: obține $10$ fericire pentru $4$ cofeină (rămân $3$ unități). Bea toată B2: obține $5$ fericire pentru $2$ cofeină (rămâne $1$ unitate). Bea o unitate din băutura lui Costel: obține $2$ fericire. Total fericire: $10 + 5 + 2 = 17$.

Pentru a doua situație ($Q = 2$):
Costel aduce o băutură cu fericire $12$ și cofeină $4$.
Bea toată băutura de la Costel: obține $12$ fericire pentru $4$ cofeină (rămân $3$ unități de cofeină). Ștefan bea o fracțiune de $3$ unități de cofeină din B1. Fericirea obținută din aceste $3$ unități va fi $7.5$. Total fericire: $12 + 7.5 = 19.5$.