Трапецієподібна доріжка
Ви плануєте встановити невелику збірну альтанку у своєму задньому дворі, з вимощеною доріжкою, що з'єднує її з вашим заднім ґанком. Доріжка буде зроблена з бруківки, яку ви придбаєте у місцевому магазині товарів для дому. Бруківка буває різних розмірів, але всі вони мають форму рівнобедрених трапецій. Як показано зліва на Рисунку 1, рівнобедрена трапеція утворюється, якщо відрізати кут рівнобедреного трикутника лінією, паралельною основі. Таку бруківку можна описати трьома параметрами: довжина одного з її паралельних країв, a, довжина іншого паралельного краю, b, і перпендикулярна відстань, h, між цими краями.
Рисунок 1: Форма рівнобедреної трапеції (зліва), приклад доріжки (в центрі) та вимоги до з'єднання (справа)
Ви плануєте побудувати доріжку, з'єднуючи паралельні краї бруківки, причому один паралельний край буде прилягати до заднього ґанку на початку, а інший - до альтанки в кінці. Ви хочете, щоб доріжка виглядала естетично, тому не дозволите жодної з ситуацій, показаних справа на Рисунку 1. Там, де дві бруківки зустрічаються, їхні краї повинні бути точно однакової довжини. Так само, де бруківка зустрічається з заднім ґанком або альтанкою, її край повинен бути точно такої ж довжини. На щастя, ваш магазин товарів для дому має широкий вибір різних трапецієподібних бруківок, тому ви впевнені, що зможете побудувати доріжку, яка задовольняє ці вимоги.
Бруківка оцінюється в два центи за квадратний сантиметр поверхні. У вас великий задній двір, тому вам не важливо, якої довжини буде ваша доріжка. Ви просто хочете, щоб вона була найдешевшою.
Вхідні дані
Вхідні дані складатимуться з декількох тестових випадків. Кожен тестовий випадок починається з додатного цілого числа, n, кількості різних типів бруківки, що є в наявності. Значення n буде щонайменше 1 і не більше 1000. Наступні n рядків кожен описує тип каменю, вказуючи довжини його сторін, a, b та h. Ці три значення будуть додатними цілими числами, виміряними в сантиметрах і не більшими за 1000. Жодні два типи каменів не є ідентичними, але ваш магазин товарів для дому має великий запас бруківки, тому ви можете купити стільки кожного типу, скільки вам потрібно. Останній рядок кожного тестового випадку вказує ширину заднього ґанку, де почнеться доріжка, а потім ширину краю альтанки, де доріжка закінчиться. Значення нуль для n позначатиме кінець усіх тестових випадків.
Вихідні дані
Для кожного тестового випадку надрукуйте загальну вартість, у доларах, для найдешевшої доріжки, яка відповідає вашим вимогам. Завжди буде можливість побудувати таку доріжку.