Задача D. Макет города ≡

Условие

У Пети на столе стоит макет центральной части города. Макет представляет собой N зданий в форме прямоугольных параллелепипедов, расположенных на плоской поверхности. Здания могут вплотную соприкасаться стенками.

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

Требуется написать программу, которая принимает на вход информацию о макете (для каждого здания известны его высота и координаты основания) и выводит искомую площадь бумаги.

Рекомендуется рассмотреть частичные решения

1. N = 1.
2. Здания не соприкасаются стенками.
3. Все здания имеют одинаковую высоту.
4. N ≤ 1000.

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

Входной файл содержит целое число N — количество зданий.

Далее следуют N пятёрок целых чисел: x_i y_i u_i v_i h_i, где (x_i, y_i) и (u_i, v_i) — координаты двух противоположных углов основания здания в сантиметрах, h_i — высота здания в сантиметрах.

Основания зданий представляют собой прямоугольники со сторонами, параллельными осям координат.

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

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

Ограничения

1 ≤ N ≤ 10⁵.

0 ≤ x_i < u_i ≤ 10000, 0 ≤ y_i < v_i ≤ 10000, 0 < h_i ≤ 100.

Сумма площадей верхних и боковых граней всех зданий без учёта соприкасающихся частей не превосходит 10⁹.

Примеры тестов

1
0 5 5 7 3

52

2
0 5 5 7 3
3 2 6 5 4

97

Разбор