Fişierul intrare/ieşire:	carti2.in, carti2.out	Sursă	Grigore Moisil 2011, Clasele 11-12
Autor	Perticas Catalin	Adăugată de	Marius Stroe •Marius
Timp execuţie pe test	0.075 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Carti2

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.

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ă.

Date de intrare

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.

Date de ieşire

Î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. 

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₁, x₂,..., x_s este mai mic lexicografic decât un alt şir y₁, y₂,..., y_t dacă există i ≤ min(s, t) astfel încât x₁ = y₁, x₂ = y₂,..., x{i-1} = y{i-1} şi x_i < y_i.

Exemplu

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.

Cum se trimit solutii?