Второй объём выдач по жанрам

Библиотека ведёт каталог выдач. Каждая строка содержит одну операцию выдачи: её номер, жанр книги и число выданных экземпляров. Несколько строк могут относиться к одному жанру, а одинаковые жанры могут встречаться много раз.

Для каждого жанра вычисляется суммарное число выданных экземпляров. Если строки жанра имеют значения copies_1, copies_2, ..., copies_k, то его агрегат равен S = copies_1 + copies_2 + ... + copies_k.

Требуется вывести второй по величине различный агрегат среди жанров. Жанры с одинаковым значением S занимают одно место. Например, если суммы равны 12, 12, 9, 4, вторым по величине различным агрегатом является 9. Если различный агрегат только один, следует вывести 0.

Формат ввода

В первой строке дано целое число n — число операций выдачи.

В следующих n строках даны три значения через пробел: loan_id, genre, copies, где loan_id — номер операции, genre — жанр книги, copies — число выданных экземпляров в этой операции.

Формат вывода

Выведите одно целое число — второй по величине различный суммарный объём выдач по жанрам или 0, если такого второго различного значения нет.

Ограничения

1 ≤ n ≤ 2000.

1 ≤ loan_id ≤ 10^9, все номера операций различны.

genre состоит только из строчных латинских букв, 3 ≤ |genre| ≤ 20.

1 ≤ copies ≤ 10000.

Пропусков в данных нет. Каждый жанр, встречающийся во входе, имеет хотя бы одну строку. Число различных жанров находится в пределах от 1 до n.