Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_29_03 - Ozdoby choinkowe

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;104] 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;109] 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.


Dodane przez:Maciej Boniecki
Data dodania:2016-08-25
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.