26807번 - Cukiernia 다국어

Cukiernia „Bajtuś” specjalizuje się w wypieku drożdżówek, pączków i rogalików. W cukierni jest n gablot z wypiekami. Na każdej z nich powinien się znajdować tylko jeden rodzaj wypieków. Powinien. . . jednak pewnego poranka do cukierni zakradł się Bajtuś – syn Bajtazara, właściciela cukierni – i pod nieobecność taty poprzestawiał wypieki między gablotami.

Za moment cukiernia powinna się otworzyć! Bajtazar chce poprzestawiać wypieki tak, aby znów w każdej gablocie był tylko jeden rodzaj wypieków. Pomóż mu i napisz program, który obliczy minimalną liczbę przestawień wypieków, która do tego doprowadzi.

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n, oznaczająca liczbę gablot.

Kolejne n wierszy opisuje gabloty: i-ty z nich, dla i = 1, . . . , n, zawiera trzy liczby całkowite d_i, p_i i r_i (0 ≤ d_i, p_i, r_i ≤ 10⁹) oznaczające odpowiednio liczbę drożdżówek, pączków i rogalików, które znajdują się obecnie w i-tej gablocie. Możesz założyć, że w cukierni znajduje się co najmniej jeden wypiek.

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita, oznaczająca minimalną liczbę przestawień wypieków między gablotami, niezbędnych do tego, aby w każdej gablocie znalazł się dokładnie jeden rodzaj wypieków. Jeśli w jakiejś gablocie ostatecznie nie będzie żadnych wypieków, to ten warunek również będzie spełniony.

Wyjaśnienie przykładu: Optymalny sposób przestawiania wypieków może wyglądać następująco:

1. Przestaw pączka z gabloty 1 do gabloty 3 i rogalika z gabloty 1 do gabloty 2.
2. Przestaw trzy pączki z gabloty 2 do gabloty 3.
3. Przestaw drożdżówkę z gabloty 3 do gabloty 1 i trzy rogaliki z gabloty 3 do gabloty 2.

W ten sposób wykonanych zostanie 9 przestawień, po których zawartość gablot będzie następująca: gablota 1: drożdżówki, gablota 2: rogaliki, gablota 3: pączki, gablota 4: drożdżówki, a gablota 5 będzie pusta.