Fidijas

UŽDUOTIS

Žymus senovės graikų skulptorius Fidijas nori pastatyti puikų monumentą. Tam reikia stačiakampių marmuro plokščių, kurių matmenys W1 ´ H1, W2 ´ H2, ..., WN ´ HN. 

Fidijas gavo didžiulį stačiakampį marmuro luitą. Šį luitą jis ruošiasi supjaustyti į reikiamo dydžio plokštes. Bet kuris marmuro gabalas (pradinis luitas arba nuo jo atpjautos plokštės) gali būti perpjautas arba horizontaliai, arba vertikaliai į du stačiakampius gabalus, kurių ilgiai ir pločiai yra sveikieji skaičiai. Tai vienintelis galimas marmuro gabalų pjaustymo būdas, be to dviejų atpjautų gabalų negalima sujungti. Kadangi marmuro luitas raštuotas, tad plokščių sukioti negalima. Jei Fidijas atpjauna A ´ B dydžio plokštę, tai jos negalima naudoti kaip plokštės B ´ A, nebent A = B. Jis gali išpjauti nulį ar daugiau kiekvieno reikiamo dydžio pokščių. Marmuro gabalas išmetamas, jei iš jo negalima išpjauti nė vieno reikiamo dydžio plokštės. Fidijui rūpi taip supjaustyti turimą luitą, kad kuo mažiau būtų išmetama. 

Panagrinėkime pavyzdį. Paveiksle pateikto luito plotis lygus 21, o aukštis – 11. Skulptoriui reikia plokščių, kurių matmenys 10 ´ 4, 6 ´ 2, 7 ´ 5 ir 15 ´ 10. Mažiausias bendras išmetamų gabalų paviršiaus plotas lygus 10. Paveiksle parodytas minimalus duoto pavyzdžio luito pjaustymo variantas.

Parašykite programą, kuri pagal turimo luito ir reikiamų plokščių matmenis rastų mažiausią bandrą išmetamų gabalų paviršiaus plotą.

PRADINIAI DUOMENYS

Pradiniai duomenys įrašyti byloje phidias.in. Pirmoje eilutėje įrašyti du sveikieji skaičiai: W ir H – duotojo luito plotis ir aukštis. Antroje eilutėje įrašytas vienas sveikasis skaičius N: reikalingų  plokščių matmenų skaičius. Tolesnėse N eilučių surašyti plokščių dydžiai. Kiekvienoje tų eilučių yra po du sveikuosius skaičius: plotis Wi ir aukštis Hi
 (1 ≤ i ≤ N). 

REZULTATAI

Rezultatų bylą pavadinkite phidias.out. Byloje turi būti viena eilutė, kurioje įrašytas vienas sveikasis skaičius: mažiausias bendras išmetamų gabalų paviršiaus plotas. 

PAVYZDŽIAI

phidias.in						phidias.out

21 11
4
10 4
6 2
7 5
15 10

10

				

RIBOJIMAI

1 ≤ W ≤ 600, 1 ≤ H ≤ 600, 0 < N ≤ 200, 1 ≤ Wi  ≤ W, ir 1 ≤ Hi ≤ H. 
50% testų, W ≤ 20, H ≤ 20 ir N ≤ 5.