carti2

Carti2

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

Poveste şi cerinţă...

Mitruţ, motanul încălţat, vrea să-şi restructureze biblioteca în aşa fel încât să-i încapă cât mai multe cărţi din cele $N$ pe care le are. Fiindcă îi place aşa de mult să doarmă, s-a gândit să-ţi dea ţie această sarcină şi promite să te recompenseze cu $100$ puncte dacă îl ajuţi. Ştii că biblioteca are înălţimea $H$ şi lăţimea $L$, iar grosimea fiecărui raft este $G$. Între oricare două rânduri adiacente de cărţi pe care le pui în bibliotecă trebuie plasat un raft. De asemenea, trebuie plasat un raft la baza bibliotecii. Cărţile pe care le deţine Mitruţ pot avea dimensiuni diferite, unele sunt mai late, altele mai înalte. Înălţimea cărţii $i$ este $A{~i~}$,  iar lăţimea ei este $B{~i~}$.
 
h2. Cerinţă
 
Determinaţi numărul maxim de cărţi care încap în biblioteca lui Mitruţ şi afişaţi cărţile pe care le puneţi în bibliotecă. Dacă sunt mai multe soluţii, afişaţi soluţia minim lexicografică. Ordinea cărţilor pe rafturi nu contează.

h2. Date de intrare

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

Pe prima linie a fişierului de intrare $carti2.in$ se află un număr natural $T$ care reprezintă numărul de teste pe care trebuie să le evaluaţi. În continuare, vor fi descrise fiecare din cele $T$ teste. Pe prima linie a fiecărui test se află numerele naturale $N$, $H$, $L$ şi $G$ cu semnificaţia din enunţ. Pe fiecare din următoarele $N$ linii se află câte două numere naturale $A{~i~}$ şi $B{~i~}$. Pe linia $i + 1$ a fiecărui test se află descrierea cărţii $i$.

h2. Date de ieşire

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

În fişierul de ieşire $carti2.out$ veţi afişa răspunsul pentru fiecare test. Pe o linie va fi numărul maxim $Nmax$ de cărţi care încap în bibliotecă, iar pe alta descrierea soluţiei optime, adică $Nmax$ numere sortate crescător după numărul de ordine al cărţilor pe care le alegeţi.

h2. Restricţii

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

* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 12$
* $1 ≤ H, L, G, A{~i~}, B{~i~} ≤ 1 000 000$
* Pentru $50%$ din teste $N ≤ 9$.
* Un şir $x{~1~}$, $x{~2~}$,..., $x{~s~}$ este mai mic lexicografic decât un alt şir $y{~1~}$, $y{~2~}$,..., $y{~t~}$ dacă există $i &le; min(s, t)$ astfel încât $x{~1~} = y{~1~}$, $x{~2~} = y{~2~}$,..., $x{i-1} = y{i-1}$ şi $x{~i~} < y{~i~}$.

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

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

| 2
8 9 7 1
3 2
6 3
7 2
3 4
2 6
4 3
1 5
5 1
8 12 13 2
6 2
3 5
7 8
2 4
9 5
3 5
2 7
6 3
| 4
1 2 7 8
5
1 2 4 6 7

|
h3. Explicaţie

...

Pentru primul test putem împărţi cele $4$ cărţi ({$1$}, $2$, $7$ şi $8$) în următorul fel: $1$, $2$ şi $8$ le punem pe primul raft, iar $7$ pe ultimul raft.
 
Pentru al doilea test putem să punem cărţile $1$, $2$ şi $6$ pe primul raft, iar pe $4$ şi $7$ pe al doilea raft.

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

5475