Uolevi on huvipuistossa n lapsen kanssa. Jokainen lapsi haluaa mennä karuselliin samaan aikaan.

Karusellissa on k hevosta, ja tiedät jokaisesta hevosesta, kuinka mielellään kukin lapsi istuu sen päällä. Mikä on suurin mahdollinen mieluisuuksien summa?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja k: lasten määrä ja hevosten määrä.

Sitten syötteessä on n riviä, joista jokaisella on k lukua. Nämä rivit kertovat kullekin lapselle jokaisen hevosen mieluisuuden.

Tuloste

Tulosta yksi kokonaisluku: suurin mahdollinen mieluisuuksien summa.

Esimerkki

Syöte:

2 3
1 4 1
1 5 3

Tuloste:

7

Selitys: Lapsi 1 istuu hevosen 2 päällä ja lapsi 2 istuu hevosen 3 päällä.

Osatehtävät

Kaikissa osatehtävissä mieluisuudet ovat välillä 1 \ldots 10^9.

Osatehtävä 1 (27 pistettä)

• 1 \le n \le 2
• n \le k \le 10^5

Osatehtävä 2 (31 pistettä)

• 1 \le n \le 14
• n \le k \le 200

Osatehtävä 3 (42 pistettä)

• 1 \le n \le 14
• n \le k \le 10^5