magnify

Milžiniškas ekranas

Pradinių duomenų failas:
ekranas.in  
Rezultatų failas:
ekranas.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Kompanija, kurioje dirbate, konstruoja ir pardavinėja milžiniškus (mažų mažiausiai tikrai didelius) ekranus. Šie milžinai konstruojami iš daugelio mažesnių ekranų. Jūs esate atsakingas būtent už klientų užsakytų ekranų suprojektavimą.

Klientai užsakydami ekraną nurodo horizontalią bei vertikalią ekrano raišką (taškais), ir horizontalų bei vertikalų ekrano dydį (milimetrais). Jūsų užduotis yra suprojektuoti ekraną, kuris būtų užsakytos arba didesnės raiškos (kiekvienoje dimensijoje) ir užsakyto arba didesnio dydžio (taip pat kiekvienoje dimensijoje), už mažiausią kainą. Ekranas-milžinas visuomet konstruojamas iš vienodo tipo mažų ekranų. Gauta raiška, dydis ir kaina yra tiesiog suma raiškų, dydžių bei kainų ekranų, iš kurių jis sukonstruotas.

Jūs turite nemažą pasirinkimą, iš kokių (mažų) ekranų konstruoti. Žinote visų jų raiškas, dydžius bei kainas. Ekranai gali būti montuojami vertikaliai arba horizontaliai, tačiau didysis ekranas turi būti sukonstruotas iš vienodo tipo ir vienodai orientuotų ekranų. Pasirinkto tipo ekranų galite užsakyti kiek tik jums reikia.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašyti keturi sveikieji skaičiai: \(r_{h}\), \(r_{v}\), \(s_{h}\) ir \(s_{v}\) (visi skaičiai yra tarp 100 ir 10000 imtinai) — tai horizontali ir vertikali raiška, bei horizontalus ir vertikalus dydis ekrano, kurį turite suprojektuoti.

Kitoje eilutėje įrašytas vienas sveikas skaičius n (1 ≤ n ≤ 100) — skaičius mažų ekranų, iš kurių galite rinktis. Sekančios n eilučių aprašo kiekvieną iš jų. Kiekvienoje eilutėje įrašyti penki sveikieji skaičiai — \(r_{h, i}\), \(r_{v, i}\), \(s_{h, i}\), \(p_{i}\) (visi skaičiai yra tarp 100 ir 10000 imtinai). Pirmieji keturi skaičiai yra i-ojo ekrano tipo horizontali ir vertikali raiška, bei horizontalus ir vertikalus dydis. O \(p_{i}\) yra i-ojo ekrano kaina.

Rezultatai

Į rezultatų failą programa turi įrašyti vienintelį skaičių — mažiausią galimą ekrano-milžino kainą.

Pavyzdžiai

Pradiniai duomenys Rezultatai
1024 1024 300 300
3
1024 768 295 270 200
1280 1024 365 301 250
1280 800 350 270 210
250
2400 2000 800 700
3
1024 768 295 270 200
1280 1024 365 301 250
1280 800 350 270 210
1260
© Bronė Narkevičienė