Fidijas

Pradinių duomenų failas:

fidijas.in  

Rezultatų failas:

fidijas.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Žymus senovės graikų skulptorius Fidijas nori pastatyti puikų monumentą. Tam reikia stačiakampių marmuro plokščių, kurių matmenys \(W_{1}\) x \(H_{1}\), \(W_{2}\) x \(H_{2}\), …, \(W_{N}\) x \(H_{N}\).

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 x B dydžio plokštę, tai jos negalima naudoti kaip plokštės B x A, nebent A = B. Jis gali išpjauti nulį ar daugiau kiekvieno reikiamo dydžio plokšč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 x 4, 6 x 2, 7 x 5 ir 15 x 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

Pirmoje pradinių duomenų failo eilutėje įrašyti du sveikieji skaičiai: W ir H – duotojo luito plotis ir aukštis (1 <= W, H <= 600). Antroje eilutėje įrašytas vienas sveikasis skaičius N – reikalingų plokščių matmenų skaičius (0 < N <= 200). Tolesnėse N eilučių surašyti plokščių dydžiai. Kiekvienoje tų eilučių yra po du sveikuosius skaičius: plotis \(W_{i}\) ir aukštis \(H_{i}\) (1 <= \(W_{i}\) <= W, 1 <= \(H_{i}\) <= H, 1 <= i <= N).

Rezultatai

Rezultatų failą turi sudaryti viena eilutė, kurioje įrašytas vienas sveikasis skaičius – mažiausias bendras išmetamų gabalų paviršiaus plotas.

Pavyzdžiai

21 11
4
10 4
6 2
7 5
15 10

10