Условие

В долине расположена линия из N платформ, пронумерованных от 0 до N - 1. Высота платформы i равна S[i].

Путешественник начинает на платформе 0 и хочет добраться до финиша, который находится в точке N — сразу за последней платформой.

Находясь на платформе i, он может совершить прыжок вперёд на расстояние от A[i] до B[i] включительно. Это значит, что с платформы i можно попасть в любую позицию j, такую что:

• i + A[i] <= j <= i + B[i].

Если j < N, то путешественник приземляется на платформу j. Если j = N, то он сразу достигает финиша.

Путешественник боится больших высот, поэтому хочет выбрать такой маршрут от платформы 0 до точки N, чтобы максимальная высота платформы, на которую он попадал по пути, была минимальной.

Требуется определить это минимально возможное значение.

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

Первая строка содержит одно целое число N — количество платформ.

Следующие N строк содержат по три целых числа S[i], A[i], B[i]:

• S[i] — высота платформы i;
• A[i] и B[i] — минимальная и максимальная длина прыжка с платформы i.

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

Выведите одно целое число:

• минимально возможную максимальную высоту платформы на маршруте от 0 до N,
• или -1, если добраться до точки N невозможно.

Ограничения

• 1 <= N <= 10^6
• 0 <= S[i] <= 10^6
• 1 <= A[i] <= B[i] <= N - i

Пояснение

Если маршрут проходит через платформы 0 -> 2 -> 5 -> N, то в ответ идёт максимум среди высот платформ 0, 2 и 5.

Нужно среди всех возможных маршрутов выбрать тот, у которого это значение минимально.

Пример 1

Ввод

4
1 1 3
3 3 3
1 1 1
2 1 1

Вывод

2

Пример 2

Ввод

6
2 2 3
1 3 4
2 1 2
3 2 3
1 1 2
1 1 1

Вывод

2