Берляндия в опасности

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 32768 KB.

ввод: input.txt
вывод: output.txt

Всем известно, что в Берляндии N городов, некоторые пары из которых соединены двусторонними дорогами. Между парой городов не может быть более одной дороги. Известно, что для любой пары городов A, B существует простой цикл, проходящий через них. Правительству известно, что вражеская империя Бирлэнд атаковала страну. Захвачен один город, отличный от столицы, но какой именно неизвестно.
Президент Берляндии решил известить жителей о предстоящей войне. Для этого он собирается отправить двух посланников. В силу специфики мировоззрения берляндцев, они будут ходить по следующему правилу. Каждому из них президент выдаст план посещения P1, P2,:, PN - перестановку целых чисел от 1 до N, P1 = 1 (столица имеет номер 1). Этот план обозначает, что посланник должен посещать города в таком порядке, но, проходя от города Pi к Pi+1, он может посещать другие города, но только те, которые он уже посещал до того.
Если посланник зайдет в захваченный город, то: он оттуда уже не выйдет. Помогите Президенту составить два таких плана, что, исполняя их, посланники могут избрать такие маршруты, что любой город будет посещен хотя бы одним из них, независимо от положения захваченного города.

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

В первой строке входного файла записано целое число N (3 <= N <= 500). Во второй -- количество дорог M. Далее в M строках описаны дороги парами номеров соединяемых городов. Города пронумерованы от 1 до N.

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

Выведите две искомые перестановки, по одной в строке.

Пример

Ввод

5
6
1 2
2 3
3 4
4 1
4 5
5 2

Вывод

1 2 3 5 4
1 4 5 3 2

Добрый и злой учитель

ограничение времени на тест: 3 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

У Саши очень добрый учитель английского языка. Он проводит в четверти всего две контрольные и ставит за четверть лучшую из оценок, полученных на контрольных. Учитель попросил Сашу написать программу, которая по результатам контрольных работ определяет четвертную оценку ученика. Саша справился с этим заданием, даже, на всякий случай, написал решение как на языке Pascal, так и на C++. Вот что у него получилось:

Var a, b: longint; begin assign(input, 'input.txt'); reset(input); assign(output, 'output.txt'); rewrite(output); read(a, b); if (a > b) then writeln(a) else writeln(b); end.

#include <stdio.h> int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); int a, b; scanf("%d %d", &a, &b); if (a > b) printf("%dn", a); else printf("%dn", b); return 0; }

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

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

Во входном файле содержатся четыре целых числа a, b, c, d (2 ≤ a,b,c,d ≤ 5) - оценки, полученные учеником за контрольные.

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

В выходной файл выведите оценку, которую ученик получит за четверть по русскому языку.

Пример

Ввод

2 3 4 5

Вывод

Гипотеза Гольдбаха

ограничение времени на тест: 3 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

Проблема Гольдбаха - это одна из самых старых, до сих пор, не разрешённых проблем математики. При этом она очень просто формулируется: Любое чётное число больше двух можно представить в виде суммы двух простых чисел.
Простое число - это натуральное число, большее единицы, имеющее ровно два натуральных делителя: 1 и само себя.
Эта гипотеза проверена для достаточно большого количества натуральных чисел. Для заданного четного натурального n определите два простых числа, сумма которых равна n. Если существует несколько вариантов, то достаточно найти любой из них.

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

Во входном файле содержится одно натуральное четное число n (4 ≤ n ≤ 100).

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

В выходной файл выведите два простых числа, сумма которых равна n. Числа разделите пробелом.

Пример

Ввод

Пример 1
14

Пример 2
14

Вывод

Пример 1
3 11

Пример 2
7 7

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

Кони

ограничение времени на тест: 3 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

Шахматным конем называется фигура, которая за один ход на клетчатом поле перемещается на 2 клетки в одном из 4 направлений (влево, вправо, вверх или вниз) и на 1 клетку в перпендикулярном. Будем говорить, что фигура контролирует клетку, если она может достичь ее за любое число ходов. Поле также может иметь бесконечную длину и/или ширину. Это означает, что поле имеет бесконечное число клеток, например поле INF* M будет представлять собой полосу бесконечной длины шириной M, а поле INF*INF - абсолютно бесконечное поле, не имеющее границ. Дано поле N*M,(1 ≤ N, M ≤ 1000 или бесконечность (INF)), найдите минимальное число коней, для того, чтобы контролировать все поле.

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

В первой строке входного файла содержится число 1 ≤ N ≤ 1000 - длина шахматного поля или слово INF (заглавными латинскими буквами), если поле имеет бесконечную длину. Во второй строке содержится число 1 ≤ M ≤ 1000 - ширина шахматного поля или слово INF (заглавными латинскими буквами), если поле имеет бесконечную ширину.

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

Выведите единственное число - ответ на поставленную задачу. Если для достижения результата требуется бесконечное количество коней, то выведите INF.

Пример

Ввод

8
8

Вывод

1
Пояснение
Это стандартная шахматная доска. Если поставить коня на клетку a1, то им можно будет обойти все клетки.

Дартс

ограничение времени на тест: 3 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

Дартс - игра, в которой игроки метают короткие стрелы (дротики) в круглую мишень, повешенную на стену.
Стандартная мишень разделена на двадцать пронумерованных секторов, каждой присвоено число от 1 до 20. В центре находится "яблочко", попадание в которое оценивается в 50 очков, окружённое зелёным кольцом вокруг него (25 очков). Внешнее узкое кольцо (кольцо "даблов") означает удвоение числа сектора, внутреннее узкое кольцо (кольцо "треблов") означает утроение числа сектора. Количество очков, получаемое за каждый сектор, указано на рисунке. Внешнее и внутреннее узкие кольца традиционно окрашиваются в красный и зелёный цвета. Попадание дротика вне круга ограниченного внешним узким кольцом очков не приносит. На стене висит мишень, причем ее центр совпадает с точкой (0, 0). Известно, что после броска, дротик застрял в точке с координатами (x, y) (все координаты описываются в миллиметрах, y - обозначает координату по вертикали, x - по горизонтали). Требуется подсчитать, сколько очков получит игрок за такой бросок. Гарантируется, что после броска дротик не попал на границу между двумя различными секторами, и можно однозначно определить количество очков, набранных игроком.

Стандартные размеры мишени:

· внутренняя ширина колец "даблов" и "треблов" 8 мм.

· внутренний диаметр "яблочка" 12,7 мм.

· внутренний диаметр внешнего центрального кольца 31,8 мм.

· расстояние от центра мишени до внешней стороны кольца "даблов" 170,0 мм.

· расстояние от центра мишени до внешней стороны кольца "треблов" 107,0 мм.

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

Во входном файле через пробел записаны два дробных числа (с 2 знаками после запятой), описывающие координаты точки.

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

Выведите единственное число - ответ на поставленную задачу.

Пример

Ввод

Пример 1
0.00 0.00

Пример 2
0.00 102.00

Вывод

Пример 1
50
Пояснение к примеру 1
Дротик попал точно в яблочко, поэтому дается 50 очков

Пример 2
60
Пояснение к примеру 2
Дротик попал в сектор 20 при этом в узкую полоску "треблов", поэтому количество набранных очков 20 * 3 = 60.

[отсортированные по размеру решения]

Выражение

ограничение времени на тест: 3 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

Вам задано арифметическое выражение, состоящее из натуральных чисел и знаков * и / (умножить и разделить) между ними. Известно, что конечный результат этого выражения является целым числом. Найдите количество делителей значения этого выражения.

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

Во входном файле содержится выражение. Числа и знаки операций отделены друг от друга ровно одним пробелом. Каждое число не превосходит 10⁸. Всего чисел не менее 1 и не более 1000.

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

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

Пример

Ввод

Пример 1
5 / 15 * 3 * 7

Пример 2
2 * 3 * 5 * 7 / 6

Пример 3
5 * 3 * 7

Вывод

Пример 1
2

Пример 2
4

Пример 3
8

Агентурная сеть

ограничение времени на тест: 3 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

Служба в разведке связана с огромными рисками. Любое неосторожное действие и даже слово может привести к раскрытию и аресту разведчика. Это знают как разведчики, так и их руководство. Если каждый агент будет знать, как найти или связаться с любым другим агентом, то один предатель может раскрыть сразу всех агентов, что недопустимо. Поэтому каждый агент может непосредственно сообщить секретную информацию только некоторым агентам (это распределение было сделано по неизвестным нам соображениям). Так как информация, которую ему удалось достать, может быть интересна всем агентам, то связи организованны таким образом, что каждый агент может передать информацию каждому (непосредственно или используя нескольких посредников). В случае ареста одного или более разведчиков это свойство может быть нарушено (то есть будет такая пара агентов, которые не смогут передавать информацию друг другу даже через посредников). Разведывательное управление интересует, может ли арест вражеской стороной k агентов привести к тому, что оставшиеся разведчики не смогут свободно передавать информацию друг другу. Ваша задача ответить на этот вопрос. В случае, если вражеская контрразведка может арестовать k агентов таким образом, то необходимо найти номера этих агентов, чтобы можно было их предупредить. Этим агентам придется быть особенно осторожными. В случае если существует несколько способов выбора агентов для ареста, то нужно вывести любой, удовлетворяющий требованию.

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

В первой строке входного файла содержатся три числа n, m и k (3 ≤ n ≤ 16, n -1 ≤ m ≤ 120, 1 ≤ k ≤ n -2) - общее количество агентов, количество линий связи и количество агентов, которых могут арестовать. Далее следует m строк, описывающих двусторонние линии связи. В каждой строке записано два различных числа x и y (1 ≤ x, y ≤ n), разделенных пробелом. Это означает, что существует двусторонняя связь между агентами x и y.

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

В выходной файл выведите k различных чисел - номера агентов, которых может арестовать вражеская сторона, чтобы какая-то пара агентов осталась без связи. Если такой арест произвести невозможно, то выведите единственное число 0.

Пример

Ввод

Пример 1
3 3 1
1 2
3 2
3 1

Пример 2
4 4 2
1 2
3 2
3 4
4 1

Пример 3
6 6 3
1 2
2 3
3 1
4 5
5 6
6 4

Вывод

Пример 1
0

Пояснение к примеру 1
Вражеской стороне разрешено арестовать только одного агента. Но при аресте любого агента двое других смогут свободно общаться.

Пример 2
1 3

Пояснение к примеру 2
Если арестуют первого и третьего агента, то 2 и 4 останутся сами по себе и не смогут никому передавать информацию, в том числе и друг другу. Ответы "3 1", "2 4" и "4 2" так же правильные.

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

Цепочка

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

Рассмотрим цепочку, состоящую из N колец. Какое минимальное количество колец необходимо расцепить, чтобы из оставшихся кусков можно было собрать цепочки любой длины от 1 до N колец? При создании новых цепочек можно использовать расцепленные кольца. Например, при N = 21, достаточно расцепить всего 2 кольца таким образом, чтобы получились куски длинной 3, 5 и 11. Два расцепленных кольца считаются кусками единичной длины.

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

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

Единственная строка входного файла содержит одно целое число N (1 ≤ N ≤ 10⁹).

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

Единственная строка выходного файла должна содержать одно целое число - найденное минимальное количество колец.

Пример(ы)

input.txt	output.txt
21	2

Деревья

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

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

Между каждой парой деревьев в саду протоптаны тропинки. Когда садовники идут от дерева к дереву, они обязательно идут по тропинке соединяющей непосредственно эти два дерева. Длина тропинки одинакова при перемещении в обе стороны.

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

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

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

Первая строка входного файла содержит целое число N (2 ≤ N ≤ 1000) - количество деревьев в саду. Каждая i -ая из последующих N -1-ой строк содержит N - i чисел, которые последовательно представляют длины тропинок между i -ым деревом и деревьями с i +1-го до N -го. Все числа целые, неотрицательные, и не превышают 10⁶.

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

Единственная строка выходного файла должна содержать одно целое число - минимальную для всех возможных разбиений сада длину самой длинной тропинки между деревьями в одной из частей сада.

Пример(ы)

input.txt	output.txt
3 1 5 1	1

439. Доставка

ограничение времени на тест: 4 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

Город Прямой Рог представляет собой одну прямую улицу. В городе работает компания, которая занимается доставкой товаров. Для удобства, адреса доставки представлены в виде чисел, которые задают расстояние от офиса компании. Положительные числа в одну сторону, а отрицательные - в другую. Заказы на доставку выполняются компанией последовательно, в том порядке, в котором они были заданы.

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

Напишите программу, которая по расстояниям адресатов от офиса компании находит наименьшее суммарное расстояние, которое пройдут ее работники.

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

Первая строка входного файла содержит целое число N (1 ≤ N ≤ 100000) - количество заказов. Далее следует N строк, каждая из которых содержит одно целое число - расстояние от офиса до адресата. Если расстояние положительное - то адресат находится в одной части города относительно офиса компании, а если отрицательное, то в другой. Расстояния по модулю не превышают 10⁸.

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

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

Пример(ы)

input.txt	output.txt
5 1 -1 2 -2 3	5

Z функция

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

"Строка S - это упорядоченный список символов, записанных подряд слева направо. Для любой строки S обозначим через S (i... j) подстроку S, которая начинается в позиции i и заканчивается в позиции j строки S. В частности, S (1... i) называется префиксом строки S, кончающимся в позиции i. "

Алфавитом A будем называть произвольное множество символов. Будем говорить, что строка S является строкой в алфавите A, если каждый символ из S принадлежит A.

"Для данной строки S и позиции i > 1 определим Z (i) как длину наибольшей подстроки S, которая начинается в позиции i и совпадает с префиксом S ".

Под Z -функцией для строки S мы будем подразумевать вектор (Z (2), Z (3),..., Z (N)), где N - количество символов в строке S.

Подсчитать Z -функцию заданной строки S совсем несложно. Поэтому мы предлагаем решить вам в некотором смысле обратную задачу - подсчитать количество строк в алфавите (a, b, c), имеющих заданную Z -функцию.

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

В первой строке входного файла задано число K = N - 1 (1 ≤ K ≤ 60), а затем K чисел - элементы Z функции (неотрицательные целые числа, не превышающие 60).

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

Единственная строка выходного файла должна содержать одно целое число - найденное количество строк.

Пример(ы)

input.txt	output.txt
2 1 0	6

441. Диски

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

Жесткий диск компьютера Пети разбит на два раздела. Первый из них содержит A мегабайт свободного места, а второй - B мегабайт. Петя хочет установить на свой компьютер новую программу, которая требует X мегабайт свободного пространства. Специально для таких случаев у Пети есть программа, написанная на языке Pascal, которая сообщает ему, хватит ли свободного места на одном из разделов.

Но теперь перед ним стоит куда более сложная задача. Ему надо установить две программы, требующие X ₁ и X ₂ мегабайт. Разумеется, программы можно устанавливать как на разные разделы, так и на один и тот же раздел. Однако нельзя часть программы установить на один раздел, а другую часть на другой раздел. Вам требуется написать программу, которая будет определять, возможно ли установить эти программы.

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

В первой строке входного файла записаны два целых числа A, B (1 ≤ A, B ≤ 100), разделенные пробелом. Во второй строке записаны целые числа X ₁, X ₂ (1 ≤ X ₁, X ₂ ≤ 100), также разделенные пробелом.

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

Выведите YES, если можно установить все программы, или NO, если этого сделать нельзя. Будьте внимательны, слова YES и NO необходимо выводить в верхнем регистре, так как написано в условии.

Пример(ы)

input.txt	output.txt
1 20 10 10	YES

input.txt	output.txt
5 6 6 6	NO

Урок физкультуры

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

На уроке физкультуры учитель решил поделить всех учеников на две команды для игры в волейбол. Для этого он сначала оценил силу игры каждого игрока. Пусть число A_i — сила игры i -ого ученика. Ученик с самым большим значением A_i становится капитаном первой команды. Ученик с самым большим значением A_i среди оставшихся игроков становится капитаном второй команды. Далее капитаны по очереди выбирают себе по игроку. Так как каждый капитан хочет создать сильную команду, то каждый раз он выбирает игрока с максимальной силой игры среди оставшихся, то есть с максимальным значением A_i.

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

Рассмотрим пример. Пусть в классе 5 игроков и их способности игры в волейбол: 1, 6, 3, 5, 9. Тогда в первую команду попадут игроки с силой 9, 5 и 1, а во вторую — 6, 3. Для данного примера ответ будет равен (9 + 5 + 1) - (6 + 3) = 6.

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

В первой строке входного файла задано натуральное число N (2 ≤ N ≤ 50) - количество учеников в классе. Во второй строке содержится N чисел, где i -ое число A_i — сила игры i -ого ученика (1 ≤ A_i ≤ 1000).

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

Выведите целое неотрицательное число - ответ на задачу.

Пример(ы)

input.txt	output.txt
5 1 6 3 5 9	6

443. Числа Фибоначчи

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

Последовательность чисел Фибоначчи начинается с чисел 1, 1, а каждое следующее число определяется, как сумма двух предыдущих. Приведем несколько первых чисел этой последовательности: 1, 1, 2, 3, 5, 8, 13,...

Назовем обобщенной последовательностью Фибоначчи последовательность, первые два элемента которой A, B, а каждое следующее по - прежнему равно сумме двух предыдущих, где A и B - положительные целые числа. Таким образом, каждая такая последовательность однозначно определяется её первыми двумя членами. Например, если A = 3, B = 4, то первые члены последовательности: 3, 4, 7, 11, 18, 29,...

Вам дано число N. Требуется найти количество обобщенных последовательностей Фибоначчи, в которых N встречается в качестве i -ого элемента, где i > 2.

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

Во входном файле содержится единственное целое число N (1 ≤ N ≤ 100000).

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

Выведите единственное число - ответ на задачу.

Пример(ы)

input.txt	output.txt
3	3

input.txt	output.txt
1	0

444. Оригинальные строки

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

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

Например, строка ababab не является оригинальной, так как её можно представить в виде ab + ab + ab. Не являются также оригинальными строки aa, abcabc, abbabb. Оригинальными, например, являются строки a, ab, abacaba.

Вам предстоит найти количество оригинальных строк заданной длины N, состоящих только из букв a и b.

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

Во входном файле содержится натуральное число N (1 ≤ N ≤ 60).

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

Выведите единственное число — количество оригинальных строк длины N.

Пример(ы)

input.txt	output.txt
1	2

input.txt	output.txt
2	2

input.txt	output.txt
10	990

За грибами

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

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

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

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

В первой строке входного файла задано целое число N (1 ≤ N ≤ 1000) — количество грибных мест в лесу. Далее в N строках содержаться координаты грибных мест. В каждой такой строке записаны два целых числа x_i, y_i, разделенные пробелом (-10000 ≤ x_i, y_i ≤ 10000).

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

В выходной файл выведите единственное число - ответ на задачу.

Пример(ы)

input.txt	output.txt
3 0 0 1 1 2 2	1

input.txt	output.txt
3 0 0 0 1 1 1	2

input.txt	output.txt
6 0 0 1 1 2 2 2 1 3 2 4 3	2

Древняя Берляндия

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

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

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

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

В первой строке входного файла содержится число N (1 ≤ N ≤ 50). Затем следует N строк по N чисел. j -ое число в (i +1)-ой строке равно длине пути между крупными городами с номерами i и j. Расстояние от города да самого себя считается равным 0, все остальные расстояния - положительные целые числа, не превышающие 255.

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

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

Пример(ы)