Равносторонние домино
Все мы знаем, что такое обыкновенное домино - оно имеет вид прямоугольной плитки, длина которой в два раза больше ширины. Плитка разделена на две равные квадратные части, в каждой из которых расположено от 1 до 6 точек. Цель игры состоит в их укладке таким образом, чтобы числа на соседних частях соседних домино совпадали.
А что если сделать домино из равносторонних треугольников, как например вот это:
Равностороннее домино имеет вид четырехугольника, состоящего из двух равносторонних треугольников. Каждый из треугольников содержит от 1 до 6 точек. Два равносторонних домино можно положить друг с другом, если прилегающие треугольники содержат одинаковое количество точек, а также если домино не перекрывают друг друга. Дополнительные домино можно укладывать только так, чтобы они прилегали к уже существующим на столе. Другими словами, две непересекающиеся группы домино не образуют допустимую укладку. Например, равносторонние домино можно уложить следующим образом:
Вам следует найти наилучшую укладку, в некотором смысле, заданного набора домино. За каждое ребро двух соседних домино будем начислять одно очко. Необходимо найти такую укладку заданного множества равностороннего домино, которая получит наибольшее количество очков.
Входные данные
Состоит из нескольких тестов. Первая строка каждого теста содержит количество равносторонних домино n (1 ≤ n ≤ 6) в наличии. Дальше следуют n строк, по два целых числа в каждой со значениями от 1 до 6 включительно. В этих строках указывается количество точек на каждой из исходных домино. Последняя строка содержит n = 0 и не обрабатывается.
Выходные данные
Для каждого теста вывести в отдельной строке наибольшее количество очков, достижимых укладкой заданного множества равносторонних домино. Если допустимой укладки не существует, то вывести ноль.