Promocja

Limit pamięci: 32 MB

Wielka bajtocka sieć supermarketów poprosiła Cię o napisanie programu symulującego koszty właśnie przygotowywanej promocji.

Przygotowywana promocja ma mieć następujące zasady:

• klient, który chce wziąć udział w promocji, wpisuje na zapłaconym przez siebie rachunku swoje dane i wrzuca go do specjalnej urny,
• pod koniec każdego dnia promocji z urny wyciągane są dwa rachunki:
  • najpierw wybierany jest rachunek opiewający na największą kwotę,
  • następnie wybierany jest rachunek opiewający na najmniejszą kwotę;
  klient, który zapłacił największy rachunek otrzymuje nagrodę pieniężną równą różnicy pomiędzy wysokością jego rachunku, a wysokością rachunku opiewającego na najmniejszą kwotę,
• aby uniknąć kilkukrotnych nagród za jeden zakup, oba wybrane wg reguł z poprzedniego punktu rachunki nie wracają już do urny, ale wszystkie pozostałe rachunki dalej biorą udział w promocji.

Obroty supermarketu są bardzo duże, możesz więc założyć, że pod koniec każdego dnia, przed wyciągnięciem rachunków opiewających na największą i najmniejszą kwotę, w urnie znajdują się co najmniej 2 rachunki.

Twoim zadaniem jest obliczenie na podstawie informacji o wysokościach rachunków wrzucanych do urny w poszczególnych dniach promocji, jaki będzie łączny koszt nagród w całej promocji.

Zadanie

Napisz program, który:

• wczyta ze standardowego wyjścia listę wysokości rachunków wrzucanych do urny w poszczególnych dniach promocji,
• obliczy łączny koszt nagród wypłacanych w kolejnych dniach promocji,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna dodatnia liczba całkowita , gdzie , oznaczająca czas trwania promocji w dniach.

W każdym z kolejnych wierszy znajduje się ciąg nieujemnych liczb całkowitych pooddzielanych pojedynczymi odstępami. Liczby w -szym wierszu pliku określają wysokości rachunków wrzuconych do urny w -tym dniu promocji. Pierwsza w wierszu liczba , , jest liczbą rachunków z danego dnia, a kolejne liczb to dodatnie liczby całkowite będące wysokościami poszczególnych rachunków, każda z tych liczb jest nie większa niż .

Łączna liczba rachunków wrzuconych do urny podczas całej promocji nie przekracza .

Wyjście

Standardowe wyjście powinno zawierać dokładnie jedną liczbę całkowitą równą łącznemu kosztowi nagród wypłacanych podczas całej promocji.

Przykład

Dla danych wejściowych:

5
3 1 2 3
2 1 1
4 10 5 5 1
0
1 2

poprawną odpowiedzią jest:

19

Autor zadania: Tomasz Waleń.