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

У дяди Вани в огороде большое поле картошки размером (1010 + 1) × (1010 + 1) квадратных метров. Поле разделено на квадратные грядки, каждая грядка занимает один квадратный метр.

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

И вот дядя Ваня вышел на поле, встал в самый центр центральной грядки поля и опрыскал эту грядку инсектицидами. Теперь он собирается сделать серию перемещений и обработать еще несколько грядок. В ходе каждого из перемещений дядя Ваня двигается влево, вправо, вверх или вниз по полю на некоторое целое количество метров. По пути дядя Ваня обрабатывает все грядки, на которые наступает. Другими словами грядки, которые имеют хоть какое-то пересечение с траекторией дяди Вани, оказываются обработанными инсектицидами.

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

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

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

В первой строке записано целое число n (1 ≤ n ≤ 1000) — количество перемещений дяди Вани.

В следующих n строках задано описание перемещений дяди Вани. В i-ой из этих строк описывается i-ое по счету перемещение. Каждое перемещение задано в формате «di xi», где di — символ, определяющий направление перемещения («L», «R», «U» или «D» для направлений «влево», «вправо», «вверх» и «вниз» соответственно), а xi (1 ≤ xi ≤ 106) — целое число, определяющее количество метров, на которое происходит перемещение.

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

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

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
5
R 8
U 9
L 9
D 8
L 2
Выходные данные
101
Входные данные
7
R 10
D 2
L 7
U 9
D 2
R 3
D 10
Выходные данные
52