У Пака Чанека есть \(n\) двухмерных ломтиков сыра. \(i\)-й ломтик сыра можно представить в виде прямоугольника размерами \(a_i \times b_i\). Мы хотим расположить их на двумерной плоскости так, чтобы:
- Каждая грань каждого ломтика сыра параллельна либо оси x, либо оси y.
- Нижняя грань каждого ломтика — это отрезок на оси x.
- Никакие два ломтика не пересекаются, но они могут соприкасаться гранями.
- Они образуют одну связанную фигуру.
Обратите внимание, что мы можем расположить их в любом порядке (крайний левый ломтик сыра не обязательно является первым ломтиком сыра). Также обратите внимание, что мы можем вращать каждый ломтик сыра любым способом при условии выполнения остальных ограничений.
Найдите минимально возможный периметр построенной фигуры.
Выходные данные
Для каждого набора входных данных выведите строку, содержащую целое число — минимально возможный периметр построенной фигуры.
Примечание
В первом наборе входных данных один из способов получения минимально возможного периметра выглядит следующим образом.
Мы можем вычислить периметр построенной фигуры: \(2+5+1+1+1+1+3+1+5+1+2+3=26\). Можно показать, что нельзя получить меньший периметр.
Ниже показано некорректное расположение.
Периметр данной фигуры \(24\), но не все ограничения в задаче выполнены. Нижняя грань ломтика \(1 \times 1\) не находится на оси x.
Во втором наборе входных данных один из способов получения минимально возможного периметра выглядит следующим образом.
Мы можем вычислить периметр построенной фигуры: \(2+2+2+3+2+3+2+2+2+4=24\). Можно показать, что нельзя получить меньший периметр.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
4 1
4 5
1 1
2 3
3
2 4
2 6
2 3
1
2 65
|
26
24
134
|