20892번 - Julklappsköp 다국어

Snälla Allnäs ska köpa en julklapp vardera till sina $K$ vänner (trots att det är februari -- Allnäs tror på att ha god marginal). Butiken hon är i har exakt ett exemplar av varje vara. Det finns totalt $N$ varor. Allnäs känner sina vänner mycket bra -- hon vet exakt vem som gillar vad och hur mycket. Hon har skrivit ner en lista med alla $a_{ij}$ tal, talen som säger hur mycket vän $i$ gillar present $j$.

Nu vill Allnäs maximera sina vänners glädje. Hon vill ge sina vänner presenter på ett sånt sätt, att summan av glädjen för varje vän (d.v.s. talen $a_{ij}$) blir maximal. Vilka julklappar ska hon köpa för att maximera summan av sina vänners glädje?

Den första raden innehåller två heltal $K$ (antal vänner) och $N$ (antal presenter).

De följande $K$ raderna innehåller $N$ heltal vardera. På den $i$:te raden är det $j$:te heltalet $0 \le a_{ij} \le 10^8$ -- hur glad den $i$:te vännen blir om den får den $j$:te presenten.

Du ska skriva ut ett heltal -- den maximala summan av vännernas glädje.

• $1 \le K \le 14$
• $1 \le N \le 100 000$