D. Салаты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Наконец, самолеты улетели, а Джефф подумал, что неплохо бы сделать перерыв в работе. В сквере неподалеку от его офиса есть летнее кафе, в котором готовят вкусные фруктовые салаты. А что может быть лучше такого салата в июньский знойный день?..

Работники кафе выяснили, что наибольшей популярностью пользуются два вида салатов, и стараются приготовить как можно больше порций именно этих салатов. Однако некоторые ингредиенты в этих салатах одинаковые.

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

Авокадо — 4 части;

Сельдерей — 1 часть;

Мандарин — 1 часть;

Зеленое яблоко — 2 части.

У работников кафе также есть список ингредиентов с указанием имеющегося в их распоряжении количества этих ингредиентов. Ваша задача — определить, какое максимальное количество порций салатов они могут приготовить.

Входные данные

В первой строке содержится целое число n, (1 ≤ n ≤ 105) — количество имеющихся ингредиентов.

В каждой из следующих n строк содержится по три целых числа: dj, fj, sj (1 ≤ dj ≤ 106,  0 ≤ fj,  sj ≤ 105,  j = 1, 2, ..., n) — имеющееся количество частей ингредиента #j, количество частей ингредиента #j, которое необходимо для приготовления одной порции первого вида салата, количество частей ингредиента #j, которое необходимо для приготовления одной порции второго вида салата. Гарантируется, что хотя бы одно из каждой пары чисел fj, sj отлично от нуля. Также гарантируется, что в состав каждого салата входит хотя бы один ингредиент.

Выходные данные

В первой строке выведите единственное целое число — максимально возможное количество порций салатов, которые удастся приготовить из имеющихся ингредиентов.

Примеры
Входные данные
7
15 4 0
7 1 2
8 1 0
12 2 2
14 0 3
10 0 2
6 0 1
Выходные данные
5
Примечание

В приведенном примере можно приготовить 3 порции салата первого вида и 2 порции салата второго вида.