Трапециевидная дорожка
Вы планируете установить небольшую сборную беседку на заднем дворе и проложить к ней дорожку из тротуарных плит, соединяющую её с задним крыльцом. Плиты, которые вы собираетесь использовать, можно приобрести в местном магазине товаров для дома. Все они имеют форму равнобедренных трапеций. Как показано слева на Рисунке 1, равнобедренная трапеция образуется, если отрезать угол равнобедренного треугольника линией, параллельной основанию. Тротуарная плита описывается тремя параметрами: длиной одного из её параллельных краёв, a, длиной другого параллельного края, b, и перпендикулярным расстоянием, h, между этими краями.
Рисунок 1: Форма равнобедренной трапеции (слева), пример дорожки (в центре) и требования к соединению (справа)
Вы собираетесь построить дорожку, соединяя параллельные края плит, при этом один край должен примыкать к заднему крыльцу в начале, а другой — к беседке в конце. Чтобы дорожка выглядела аккуратно, вы не допустите ситуаций, показанных справа на Рисунке 1. Там, где две плиты соединяются, их края должны быть одинаковой длины. Также, где плита соединяется с крыльцом или беседкой, её край должен быть такой же длины. К счастью, в вашем магазине есть большой выбор плит, поэтому вы уверены, что сможете построить дорожку, соответствующую этим требованиям.
Плиты стоят два цента за квадратный сантиметр площади. У вас большой задний двор, поэтому длина дорожки вас не беспокоит. Вы просто хотите, чтобы она была наименее дорогой.
Входные данные
Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай начинается с положительного целого числа n, обозначающего количество различных типов доступных плит. Значение n будет не менее 1 и не более 1000. Следующие n строк описывают тип плиты, указывая длины её сторон a, b и h. Эти три значения — положительные целые числа, измеренные в сантиметрах и не превышающие 1000. Ни один из типов плит не идентичен другому, но в вашем магазине есть большой запас плит, поэтому вы можете купить столько, сколько нужно каждого типа. Последняя строка каждого тестового случая указывает ширину заднего крыльца, где начнётся дорожка, и ширину края беседки, где она закончится. Значение ноль для n будет означать конец всех тестовых случаев.
Выходные данные
Для каждого тестового случая выведите общую стоимость, в долларах, для наименее дорогой дорожки, которая соответствует вашим требованиям. Всегда будет возможно построить такую дорожку.