Loading [MathJax]/jax/output/CommonHTML/jax.js

Задача A. Разрезанная рамка

Автор:А. Кленин   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Прямоугольная рамка была разрезана на N кусков. Каждый кусок может представлять собой либо отрезок прямой, либо "уголок" — два отрезка, соединённых под прямым углом.

По данным длинам отрезков требуется восстановить исходную рамку или определить, что это невозможно. Куски можно поворачивать, но нельзя отражать. Требуется использовать все куски.

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

Входной файл содержит число кусков N, за которым следуют N пар целых чисел aibi, описывающих длину двух отрезков "уголка" i-го куска. Если кусок является отрезком, то ai=0 либо bi=0.

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

Выходной файл должен содержать два положительных целых числа WH — ширину и высоту рамки, при этом WH. Если решения не существует, следует выдать число 1. Если решений несколько, следует выдать решение с максимальным значением W.

Ограничения

1N10, 0ai,bi100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10
1 1  1 1
1 0  1 0  1 0  1 0
0 2  0 2  0 2  0 2
7 1
2
5
1 1  1 1  1 1  1 1  5 0
-1

0.094s 0.008s 17