Meeting
Турнир за Купата на Декана, 2013
Time Limit: 0.5s, Memory Limit: 64MiB
Както се оказа, в днешно време не е лесно да се организира "държавен" митинг на поддръжниците на дадена партия. Особено ако това са партиите на Binary Search Programmers и Dynamic Programming Specialists. Сега лидерът на първата Stacknishev и неговият добър приятел O(N)resharski имат известни проблеми със своите привърженици.
Макар и след усилено търсене из най-затънтените части на страната все пак да успяха да съберат известно количество хора, както и да ги доведат в столицата с магически-появили се автобуси и влакове, проблемът с парадното изминаване на 200-тина метра все пак остава. Голяма част от поддръжниците им са на преклонна възраст, с психични отклонения, или от различни малцинствени групи. В следствие на това са се разделили на N на брой групи, съдържащи, съответно, A1, A2, …, AN човека. Всяка група съдържа по не повече от M човека.
За да не се получават ексцесии (а също и за да се помага на възрастните хора и да се припомня на малцинствата, имащи проблеми с българския език, какво точно трябва да се скандира) са доведени K милиционера. Сега въпросът е как те да бъдат разпределени по групите по оптимален начин.
Ели, макар и противник на управлението на тези партии, е загрижена за благосъстоянието на горките хора. Все пак, за да гласуват за тези партии, те си имат достатъчно проблеми на главата. Сега тя е решила да предостави на правителството програма, която по дадена "оценка" на това колко добре е за група с X човека да има Y пазещи я милиционера, определя колко е най-високата сумарна оценка, която може да се постигне. Не е задължително всички милиционери да бъдат ползвани за пазенето на поддръжниците.
Макар и след усилено търсене из най-затънтените части на страната все пак да успяха да съберат известно количество хора, както и да ги доведат в столицата с магически-появили се автобуси и влакове, проблемът с парадното изминаване на 200-тина метра все пак остава. Голяма част от поддръжниците им са на преклонна възраст, с психични отклонения, или от различни малцинствени групи. В следствие на това са се разделили на N на брой групи, съдържащи, съответно, A1, A2, …, AN човека. Всяка група съдържа по не повече от M човека.
За да не се получават ексцесии (а също и за да се помага на възрастните хора и да се припомня на малцинствата, имащи проблеми с българския език, какво точно трябва да се скандира) са доведени K милиционера. Сега въпросът е как те да бъдат разпределени по групите по оптимален начин.
Ели, макар и противник на управлението на тези партии, е загрижена за благосъстоянието на горките хора. Все пак, за да гласуват за тези партии, те си имат достатъчно проблеми на главата. Сега тя е решила да предостави на правителството програма, която по дадена "оценка" на това колко добре е за група с X човека да има Y пазещи я милиционера, определя колко е най-високата сумарна оценка, която може да се постигне. Не е задължително всички милиционери да бъдат ползвани за пазенето на поддръжниците.
Вход
На първия ред на стандартния вход ще бъдат зададени три цели числа N, M, и K – съответно броя групи, максималния брой хора във всяка група, и броя милиционери, които са на разположение. Следва ред с N цели числа A1, A2, …, AN – броя хора във всяка от групите. Следват М на брой реда, всеки съдържащ по K+1 числа. Числото Bij на j-та позиция в i-тия ред (индексирано от 1) указва каква е оценката ако има j-1 милиционера в група с i човека. Тоест, възможно е да има нула разпределени милиционера в някои от групите
Изход
На единствен ред на стандартния изход изведете едно цяло число – каква е максималната сумарна оценка, която може да се получи при оптимално разпределение на не повече от K милиционера измежду групите.
Ограничения
- 1 ≤ N, K, M ≤ 500
- 1 ≤ Ai ≤ M
- -1000 ≤ Bij ≤ 1000
Примерен Вход | Примерен Изход |
---|---|
5 7 10 3 1 5 5 7 4 0 -3 -6 -8 -9 -9 -9 -9 -9 -9 -2 1 1 -3 -4 -5 -6 -7 -8 -9 -10 -5 3 5 1 5 2 2 2 2 2 2 4 2 4 2 4 2 4 2 4 2 4 -19 10 12 12 7 3 -2 -13 -20 -30 -40 0 0 0 0 0 0 0 0 0 0 0 5 1 1 3 5 8 13 13 14 15 17 | 42 |
3 3 3 3 3 3 0 0 0 0 0 0 0 0 -1000 1 500 1000 | 3 |
В първия пример има 5 групи с хора, съдържащи, съответно, 3, 1, 5, 5, и 7 човека. Измежду тях могат да бъдат разпределени до 10 милиционера. Оптималното разпределение в случая е в първата група (с 3 човека) да се сложи един милиционер (давайки "печалба" към оценката 3), във втората група (с 1 човек) да не се слага милицонер (с печалба 4), в третата група (с 5 човека) да се сложат два милиционера (с печалба 12), в четвъртата група (отново с 5 човека) да се сложи един милиционер (с печалба 10) и в последната група (със 7 човека) да се сложат 6 милиционера (с печалба 13). Общата печалба става 3 + 4 + 12 + 10 + 13 = 42.