Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Жетонска игра се игра у \(N\) рунди: \(M\) такмичара распореде своје жетоне у \(N\) гомила и у свакој рунди се пореди број жетона сваког такмичара. Свака рунда се игра у виду турнира (свако са сваким), при чему побеђује играч са већим бројем жетона и у \(i\)-тој рунди победник при једном пређењу добија \(s_i\) поена (ако нема победника, нико не добија поене).
Ми се последњи прикључујемо игри и некако смо успели да сазнамо како су сви остали такмичари распоредили своје жетоне. На располагању имамо \(K\) жетона. Одредити неки распоред наших \(K\) жетона који максимизује број поена које можемо да остваримо.
У првом реду стандардног улаза налазе се позитивни цели бројеви \(N\), \(M\) и \(K\), где је \(N\) број рунди, \(M\) такмичара, а \(K\) број жетона које ми поседујемо.
У наредном реду, налази се \(N\) ненегативних целих бројева, од којих је \(i\)-ти број \(s_i\), број поена које добије победник при једном поређењу у једној рунди.
Наредних \(N\) редова налази се по \(M\) ненегативних целих бројева, \(j\)-ти број у \(i\)-том реду је \(a_{i,j}\), број жетона које је \(j\)-ти играч расподелио у \(i\)-тој рунди.
У једином реду стандардног излаза исписати највећи могући број поена које је могуће остварити при оптималном распоређивању \(K\) жетона у \(N\) рунди.
2 3 10
1 3
3 0 7
8 5 110Уколико наших \(10\) распоредимо тако што \(1\) искористимо у првој рунди, а преосталих \(9\) у другој рунди, победићемо у једном поређењу у првој рунди и у сва три поређења у другој рунди. На тај начин добићемо укупно \(1 \cdot 1 + 3 \cdot 3 = 10\) поена.
3 2 10
3 4 5
5 6
9 3
1 911