Задача “Урок физкультуры”

На уроке физкультуры тренер Сергей Петрович выстраивает учеников в одну шеренгу. В шеренге сначала идут мальчики, а потом девочки. При этом мальчики в шеренге стоят по невозрастанию роста, аналогично девочки тоже стоят по невозрастанию роста. Таким образом, следом за самым низким мальчиком стоит самая высокая девочка.

Сергея Петровича заинтересовал вопрос, какое максимальное различие в росте двух стоящих рядом учеников. Напишите программу, которая поможет Сергею Петровичу ответить на этот важный для него вопрос.

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

Первая строка содержит целое число n – число учеников в классе

(2n25). Следующие n строк содержат по два целых числа каждая:

ai и hi – пол и рост в сантиметрах i-го ученика

(ai равно 0 или 1, 100hi ≤ 200).

Значение ai = 0 означает, что i-й ученик – мальчик, а значение ai = 1 означает, что i-й ученик – девочка.

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

Выведите одно число – максимальное различие в росте стоящих рядом учеников после того, как они выстроятся в шеренгу на уроке физкультуры.

Пример

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

0 120

1 130

1 142

1 115

0 145

0 134

22