Сите знаат дека во аптеките шишињата мора да се наредени по големина (волумен), т.е. во еден ред не смее поголемо шише да се најде лево од помало шише. Од таму доаѓа и фразата „аптекарски шишиња“.

Во аптеката на Перо шишињата се наредени на N полици во M колони. Но, Перо е немарен, па шишињата ги нема наредено како што треба.

Доаѓа инспекторот за аптеки, па Перо мора да среди шишињата на полиците да се во бараниот редослед. За да не добие казна тој мора да има барем K средени полици и тој ќе среди точно толку. Перо смее да прави само една операција: Одбира една колона и ги трга шишињата од таа колона (ги крие во складот позади). Тоа може да го повтори повеќе пати.

Ваша задача е да направите програма која, за дозволената операција на отстранување колони, ќе пресмета кој е најголемиот можен вкупен волумен на сите шишиња што би останале во некои K редови, како и кои се тие редови.
Во одговорот се дава вкупниот волумен и редните броеви на избраните K редови, имајќи предвид дека најгорниот ред има реден број 1. Доколку има повеќе решенија со ист вкупен волумен, отпечатете го лексикографски најмалото од нив.

Влез

Во првиот ред се дадени бројот на полици N (1 ≤ N ≤ 4), бројот на колони M (1 ≤ M ≤ 1000) и бројот на барани средени полици K (1 ≤ K ≤ N).

Во следните N редови се дадени по M броеви A_ij (1 ≤ A_ij ≤ 100 000), кои го означуваат волуменот на шишето на полица i во колона j.

Забелешка.
За 30% од поените, важи: N = 1
За други 30% од поените, важи: K = N

Излез

Во првиот ред од излезот, отпечатете го вкупниот волумен на сите останати шишиња во K-те средени полици.

Во вториот ред, отпечатете K бројки кои ги означуваат редните броеви на средените полици во растечки редослед. Најгорната полица е означена со реден број 1, а најдолната со реден број N. Доколку постојат повеќе решенија, отпечатете го лексикографски најмалото.

Ограничувања

Временско ограничување: 200 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
3 3 2
5 2 7
5 2 7
1 1 1

излез
24
1 2

влез
3 3 2
7 2 7
7 2 7
7 2 7

излез
28
1 2

Објаснување за првиот пример:
Најоптимално е Перо да ги остави првата и втората полица, и да ја избрише втората колона. Со тоа, ќе му останат шишиња со волумен 5 и 7 на секоја од двете полици, па вкупниот збир е еднаков на 24.

Објаснување за вториот пример:
Не е важно кои 2 полици Перо ќе ги одбере бидејќи сите даваат резултат 28 (по бришење на втората колона). Меѓутоа, од можните решенија (1, 2), (2, 3), (1, 3), низата (1, 2) е лексикографски најмала.