AlgoLiga 2018

Prawdziwym hitem nadchodzących świąt Bożego Narodzenia będą ozdoby choinkowe do składania, w kształcie binarnych drzew poszukiwań. W każdym pudełku znajduje się k bombek choinkowych z nadrukowanymi liczbami oraz elementy do ich łączenia. Proces składania polega na wyciąganiu bombek po kolei z pudełka i dołączaniu ich do dotychczas utworzonej konstrukcji zgodnie z zasadami wstawiania wartości do drzewa poszukiwań binarnych. W pudełku nie ma dwóch bombek z nadrukowanymi takimi samymi liczbami. Cena każdej ozdoby równa jest sumie liczb nadrukowanych na bombkach.

Jan wybrał się do lokalnego marketu w celu zakupu ozdób. Nasz bohater wie, że to jakie liczby są nadrukowane na bombkach nie ma żadnego znaczenia, bo ludzie będą zwracać uwagę tylko i wyłącznie na kształt drzewa. W związku z tym Jan postanowił, że spośród n ozdób oferowanych w markecie chce wybrać po jednej z każdego kształtu. Jako, że nasz bohater jest oszczędny to łączny koszt wybranych drzew powinien być minimalny.

Pomóż Janowi, oblicz ile ozdób powinien kupić i jaki będzie ich łączny koszt.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite n ∈ [1;10⁴] oraz k ∈ [1;10] opisane w treści zadania.

W kolejnych n liniach znajdują się opisy ozdób. Opis każdej z nich składa się z k liczb całkowitych z zakresu [1;10⁹] odpowiadających liczbom nadrukowanym na kolejnych dodawanych bombkach.

Wyjście

Na wyjściu należy wypisać liczbę ozdób jakie powinien zakupić Jan oraz ich łączny koszt.

Przykład

Wejście:

6 4
5 3 8 9
6 3 1 5
2 1 3 4
17 12 8 16
7 5 11 13
23 25 27 29

Wyjście:

3 129

Wyjaśnienie do przykładu:

Dostępnych mamy 6 różnych ozdób choinkowych:

1.   5
    / \
   3   8
        \
         9
   

2.     6
      /
     3
    / \
   1   5
   

3.   2
    / \
   1   3
        \
         4
   

4.      17
       /
     12
    /  \
   8    16
   

5.   7
    / \
   5   11
         \
          13
   

6. 23
     \
      25
        \
         27
           \
            29
   

Jak widać możemy wyróżnić trzy różne kształty drzew. Pierwszy z nich reprezentują ozdoby o numerach 1, 3, 5. Druga grupa to drzewa 2 oraz 4. Ostatni kształt reprezentuje ozdoba o numerze 6. Z pierwszej grupy najtańsze jest drzewo numer 3 o koszcie 10. Z drugiej grupy powinniśmy wybrać ozdobę numer 2 o koszcie 15. W przypadku ostatniego kształtu nie mamy wyboru i musimy wziąć drzewo numer 6 o koszcie 104. Łączny koszt zakupionych przez nas ozdób wyniesie zatem 10 + 15 + 104 = 129.