Районная олимпиада по информатике 2021 года за 9 класс | Казахстанские олимпиады

Задача C. ICPC

Новое правило в чемпионате мира по программированию ICPC: можно использовать три компьютера.

Давайте посмотрим как это повлияла на одну из сильнейших команд с Казахстана. Кирилл, Айбар и Султан начали писать контест.

В контесте всего $n$ задач и длится 5 часов.

Они уже оценили время которое они потратят на каждую задачу. Кирилл решает задачу с номером $i$ за $a_i$ минут. Айбар за $b_i$. Султан за $c_i$.

Как и всегда нужно решить как можно больше задач с меньшим штрафом.

Штраф определяется как сумма времени решения для каждой принятой задачи.

Например, если команда сдаст первую задачу на $5$ минуте, а вторую на $10$ минуте то штраф будет равен $5 + 10 = 15$.

Вам нужно определить какой самый лучший результат может получить команда.

Формат входного файла

В первой строке дано одно целое числа $n$ ($1 <= n <= 10$) - количество задача на контесте.

В следующих $n$ строк даны по три числа $a_i$, $b_i$ и $c_i$ $(1 <= a_i, b_i, c_i <= 500)$ - время которое Кирилл, Айбар и Султан потратят на задачу соответственно.

Формат выходного файла

Выведи максимальное количество задач и минимальный штраф.

Примеры

Вход

2
1 123 345
300 301 301

Выход

2 423