Рівносторонні доміно
Усі ми знаємо, що таке звичайне доміно — це прямокутна плитка, довжина якої вдвічі більша за ширину. Плитка розділена на дві рівні квадратні частини, в кожній з яких розташовано від 1 до 6 точок. Мета гри полягає в тому, щоб укладати їх так, щоб числа на сусідніх частинах сусідніх доміно збігалися.
А що, якщо зробити доміно з рівносторонніх трикутників, як, наприклад, ось це:
Рівностороннє доміно має вигляд чотирикутника, що складається з двох рівносторонніх трикутників. Кожен з трикутників містить від 1 до 6 точок. Два рівносторонніх доміно можна покласти поруч, якщо прилеглі трикутники містять однакову кількість точок, і якщо доміно не перекривають одне одного. Додаткові доміно можна укладати лише так, щоб вони прилягали до вже існуючих на столі. Іншими словами, дві неперетинаючі групи доміно не утворюють допустиму укладку. Наприклад, рівносторонні доміно можна укласти наступним чином:
Вам слід знайти найкращу укладку, в деякому сенсі, заданого набору доміно. За кожне ребро двох сусідніх доміно нараховується одне очко. Необхідно знайти таку укладку заданого множини рівностороннього доміно, яка отримає найбільшу кількість очок.
Вхідні дані
Складається з декількох тестів. Перша рядок кожного тесту містить кількість рівносторонніх доміно n (1 ≤ n ≤ 6) в наявності. Далі слідують n рядків, по два цілих числа в кожному, зі значеннями від 1 до 6 включно. У цих рядках вказується кількість точок на кожному з вихідних доміно. Останній рядок містить n = 0 і не обробляється.
Вихідні дані
Для кожного тесту виведіть в окремому рядку найбільшу кількість очок, досяжних укладкою заданого множини рівносторонніх доміно. Якщо допустимої укладки не існує, виведіть нуль.