sate2

Sate2

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

Poveste şi cerinţă...

Se cunoaşte un regat feudal organizat sub forma a $N$ cătune. În fiecare cătun trăiesc locuitori astfel încât numărul total de locuitori din regatul feudal este $M$. După invazia poporului migrator vecin, se doreşte reorganizarea celor $N$ cătune în $K$ sate astfel: a) fiecare sat să conţină câtul împărţirii lui $M$ la $K$ locuitori b) fiecare cătun să fie inclus într-un singur sat. Un cătun este inclus într-un sat dacă toţi locuitorii cătunului respectiv aparţin satului. Odată ce un cătun va aparţine unui sat, acesta nu poate sa mai aparţina şi unui alt sat. Decideţi dacă este posibilă reorganizarea regatului feudal.

h2. Date de intrare

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

Datele de intrare se citesc din fişierul $sate2.in$.
Pe prima linie se află numărul de teste $T$.
 
Fiecare test conţine pe prima linie 3 numere naturale:
 
* $N$ - numărul de cătune,
* $M$ – numărul total de locuitori din regatul feudal,
* $K$ – numărul de sate care se doresc formate.
 
Pe următoarea linie se află N numere naturale reprezentând numărul de locuitori din fiecare cătun.

h2. Date de ieşire

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

Fişierul de ieşire $sate2.out$ cuprinde, pentru fiecare test, o singură linie conţinând raspunsul "$DA$" sau "$NU$" (fără ghilimele), atunci când se poate reorganiza regatul feudal sau nu.

h2. Restricţii

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

* 1 ≤ T ≤ 11
* 1 ≤ N ≤ 3000
* 1 ≤ M ≤ 90000
* $K = 3$ sau $4$
* Valorile pentru numărul de locuitori din fiecare cătun sunt numere naturale din intervalul $[1,  10.000]$. Pot exista mai multe cătune cu acelaşi număr de locuitori.

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

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

| 2
9 60 3
2 2 10 6 1 10 14 11 4
9 60 4
2 2 10 6 1 10 14 11 4
| DA
 NU

|

h3. Explicaţie
 
...
 

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