Gifts
Турнир за Купата на Декана, 2014
Time Limit: 0.7s, Memory Limit: 64MiB
Коледа наближава и е крайно време Ели да напазарува подаръци. Както всяка година, тя ще подари N подаръка на нейните N най-добри приятели. Тя е твърдо решена да не подарява един и същ подарък на двама човека, за това можем да считаме, че всеки подарък е уникален. Така момичето има избор измежду M подаръка (NM).

Ели е изготвила списък кой подарък каква радост ще донесе на всеки от нейните приятели и е дала тази информация в таблица с N реда и M колони (цели числа, като Aij показва колко ще се зарадва човек i на подарък j). Сега остава да избере кои подаръци да вземе и кой на кого да подари. От вас се иска да й помогнете в това начинание, като намерите оптималното разпределение.
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа N и M – съответно броя приятели и броя подаръци, измежду които избира Ели. Следват N на брой реда, всеки съдържащ по М числа Aij – радостта, която ще донесе на i-тия човек j-тият подарък. Разбира се, това число може и да е отрицателно – досещате се колко ще са "радва" момиче, получило поялник, или момче, получило сутиен за подарък.
Изход
На стандартния изход изведете едно цяло число – максималната сума от стойностите на радост на всеки от приятелите на Ели при оптимален избор и разпределение на подаръците.
Ограничения
  • 1 ≤ NM ≤ 500
  • -1,000,000 ≤ Aij ≤ 1,000,000
Примерен Вход Примерен Изход
5 8 75 391 219 256 233 179 0 244 -41 259 -91 150 364 249 -14 175 0 112 301 226 257 80 136 267 -22 45 0 -13 9 -78 -33 -105 90 190 -64 141 95 15 -68 294 1337
Тук би било оптимално Ели да подари втория подарък на първия човек (+391), петия подарък на втория човек (+364), третия подарък на третия човек (+301), четвъртия подарък на четвъртия човек (-13), и осмия подарък на петия човек (+294) = 1337.
Мрън!