A - Khepri II.Časový limit: 3s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Rozhodnutie mladého faraóna Chufeva byť pochovaný v pyramíde ešte väčšej a majestátnejšej ako všetky predošlé ovplyvnilo celý vtedajší Egypt. Pyramídy sa v tých časoch stavali z vápencových blokov v tvare kvádra a na stavbu tej Chufevovej sa ich použilo viac ako dva milióny. Aj Khepri, vtedajší majiteľ kameňolomu na východnom brehu Nílu, sa tak stal dodávateľom kvádrov na túto stavbu. Faraónovo rozhodnutie prinútilo Khepriho okamžite zrušiť dodávky kvádrov do ostatných stavieb vtedajšieho Egypta a všetky dostupné kvádre presmerovať na stavbu pyramídy. Architekti ale pri stavbe pyramídy využívajú len niekoľko typov kvádrov. Kvádre iných rozmerov sa na stavbu použiť nedajú a sú pre nich bezcenné. Avšak Khepri mal v zásobe príliš veľa takýchto kvádrov, pôvodne vyrobených na iné stavby Egypta. Hoci kamenárstvo v tých dobách zažívalo výrazný pokrok, vápencové kvádre boli ťažko spracovateľné. Jedinou vecou, ktorú vtedy kamenári dokázali s vápencovým kvádrom urobiť, bolo rozrezať kváder na dve (nie nutne rovnaké) časti, rovnobežne s jednou z jeho stien. Kedže kamenári sú Khepriho otroci, takýchto operácií môže vykonať ľubovoľne veľa. ÚlohaNa stavbu pyramíd sa používa M typov kvádrov s celočíselnými rozmermi a celočíselnou cenou za kus. Khepri má v sklade N kvádrov s celočíselnými rozmermi. Zistite maximálnu cenu, za akú môže Khepri svoje kvádre predať.VstupPrvý riadok vstupu obsahuje medzerou oddelené celé čísla M N. (1≤M≤50),(1≤N≤1000).Ďalej bude nasledovať M riadkov popisujúcich typy kvádrov používaných na stavbu pyramídy. Každý z týchto riadkov bude obsahovať 4 kladné celé čísla a b c w, kde a,b,c sú dĺžky hrán kvádra a w je cena, za ktorú sa dá takýto kváder predať. (1≤a,b,c≤50), (1≤w≤10*a*b*c). Môžete predpokladať, že predať sa dá neobmedzene veľa takýchto kvádrov. Posledných N riadkov vstupu bude popisovať Khepriho kvádre. Každý z týchto riadkov bude obsahovať 3 kladné celé čísla a b c, určujúcich dĺžky hrán kvádra. (1≤a,b,c≤50). VýstupVýstupom má jediný riadok (ukončený znakom EOLN), určujúci maximálnu cenu za akú dokáže Khepri svoje kvádre predať.PríkladPríklad vstupu3 4 1 1 1 5 1 1 1 4 2 2 2 50 6 4 4 3 2 1 8 8 8 3 4 5 Príklad výstupu4170 |