L'o

Dupa o vara apriga de cules castraveti murati, au ramas de redistribuit recoltele la Bastion. Sunt un numar infinit de ferme de castraveti murati, doar $N$ dintre care au avut recolte nenule in acest an. Acestea sunt puse in mod convenient pe o linie, astfel ca ferma cu numarul $i$ este pusa la $i$ $unitati agricole$ la dreapta de Bastion. A $i$-a ferma isi poate redistribui recoltele in urmatorul mod: daca are *exact* $i$ castraveti murati, acestia vor fi impartiti in mod egal intre toate fermele aflate intre Bastion si ferma $i-1$ (i.e. fiecare primeste cate un castravete murat, pe cand ferma $i$ ii pierde pe toti)

Dupa o vara apriga de cules castraveti murati, au ramas de redistribuit recoltele la Bastion. Sunt un numar infinit de ferme de castraveti murati, doar $N$ dintre care au avut recolte nenule in acest an. Acestea puse in mod convenient pe o linie, astfel ferma numarul $i$ este pusa la $i$ $unitati agricole$ la dreapta de Bastion. A $i$-a ferma isi poate redistribui recoltele in urmatorul mod: Daca are *exact* $i$ castraveti murati, acestia vor fi impartiti in mod egal intre toate fermele la stanga celei $i$ si Bastion (i.e. fiecare primeste cate un castravete murat, pe cand ferma $i$ ii pierde pe toti)

Scopul programului de Consolidare a Actiuniilor de Redistributie Nationala a Exploatariilor Agricole e de a aduce *toti* castravetii murati din provincie in Bastion pentru o ulterioara reredistributie. Programul esueaza daca un numar de castraveti murati raman in provincie fara a putea fi redistribuiti in modul convenit. Determinati daca programul guvernului Ghoberman esueaza sau va reusi.

Fişierul de intrare $marioneta.in$ contine pe primul test un numar, $T$, indicand ca vor fi de rezolvat $T$ scenarii diferite. Fiecare scenariu va avea urmatoarea forma:

Pe prima linie contine $N$, reprezentand numarul de ferme cu recolta nenula. Urmeaza $N$ linii, pe fiecare din ele aflandu-se doua numere $P{~i~}$ si $C{~i~}$, reprezentand ca ferma numarul $P{~i~}$ a strans o recolta de $C{~i~}$ castraveti murati

Pe prima linie contine $N$, reprezentand numarul de ferme cu recolta nenula. Urmeaza $N$ linii, pe fiecare din ele aflandu-se doua numere $C{~i~}$ si $P{~i~}$, reprezentand ca ferma numarul $P{~i~}$ a strans o recolta de $C{~i~}$ castraveti murati

h2. Date de ieşire
În fişierul de ieşire $marioneta.out$ se va afisa, pentru fiecare scenariu, $1$ daca programul guvernului va functiona, $0$ daca nu

h2. Restricţii și subtask-uri
 
* $1 ≤ T ≤ 20$
* $0 ≤ C{~i~} ≤ 10^9^$
* $1 ≤ N$
* $1 ≤ P{~i~} ≤ 1.000.000$
* Fie $S = C{~1~} + C{~2~} + ...$
 
table(subtask-uri). |_. Subtask |_. Punctaj |_. Restricții |
| 1 | 11 puncte | $N ≤ 400$ și $S ≤ 5000$ |
| 2 | 14 puncte | $N ≤ 1.000$ |
| 3 | 21 puncte | $N ≤ 6.000$ și $S ≤ 10^7^$ |
| 4 | 26 puncte | $N ≤ 10.000$ |
| 5 | 28 puncte | $N ≤ 50.000$ |

h2. Restricţii
* $... ≤ ... ≤ ...$

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

| 3
  1
  2 2
  2
  3 2
  4 4
  1
  3 3
| 1
  1
  0

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

|

h3. Explicaţie
 
...

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