vmin

Vmin

== include(page="template/taskheader" task_id="vmin") ==

Poveste şi cerinţă...

Se dau $N$ functii liniare de forma $A * T + B$. Sa se determine pentru $M$ query-uri, care este functia de valoare minima la un moment oarecare $T$. Query-urile se dau in ordine crescatoare dupa $T$.

h2. Date de intrare

Fişierul de intrare $vmin.in$ ...

Fişierul de intrare $vmin.in$ va contine pe prima linie doua numere naturale $N$ si $M$. Pe urmatoarele $N$ linii se vor gasi $N$ perechi de numere intregi, reprezentand valorile $A$ si $B$ pentru fiecare functie. Pe linia $N+2$ se vor gasi $M$ elemente, reprezentand momentele de timp pentru care trebuie sa determinam functia de valoare minima.

h2. Date de ieşire

În fişierul de ieşire $vmin.out$ ...

În fişierul de ieşire $vmin.out$ se vor gasi pe o singura linie $M$ valori, reprezentand raspunsurile la cele $M$ query-uri. Raspunsul la un query este reprezentat de indicele functiei de valoare minima la acel moment.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 1 000 000$
* $-10^9^ ≤ A,B ≤ 10^9^$
* $0 ≤ T ≤ 10^9^$
* Pentru teste in valoare de $40p$, $N ≤ 1000, M ≤ 3000$

h2. Exemplu
table(example). |_. vmin.in |_. vmin.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 3
4 5
2 9
8 7
11 3
0 5 7
| 4 2 2

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="vmin") ==

7944