Торговец
Торговец владеет тремя видами товаров: алмазы, яблоки и шелк. Для каждого товара известна стоимость в золотых монетах за единицу веса и его количество у торговца.
В стране, где живет торговец, есть N городов, которые пронумерованы от 1 до N. Родной город торговца имеет номер 1, а столица - номер N. Чтобы добраться до столицы, где торговец может продать товар, ему нужно проехать определенным маршрутом через другие города. Между некоторыми парами городов существуют дороги, проезд по которым стоит определенного количества золотых. В каждом городе взимается налог за провоз каждого из видов товара, заданный в процентах от стоимости провезенного через город товара. Известно, что выехав из любого города, торговец не может в него вернуться. Любые два города соединены не более чем одной дорогой.
Задача торговца получить наибольшую прибыль - разницу полученных в столице денег за проданный товар и расходов на путешествие в столицу. Он не обязан брать с собой весь свой товар. Торговец всегда имеет достаточно золотых для уплаты налогов, и не может рассчитаться товаром, который он везет в столицу. Все дороги ведут только в одном направлении.
Напишите программу, которая по информации о количестве единиц веса разных видов товара у торговца, цене на эти товары в столице, налогах в городах, дорогах между городами и стоимости проезда по этим дорогам установит максимальную прибыль, которую может получить торговец от реализации товара.
Входные данные
Первая строка содержит два целых числа N (2 ≤ N ≤ 500) и M (M ≥ 1) - количество городов и дорог между ними. Вторая строка содержит три целых неотрицательных числа, которые соответствуют количествам единиц веса алмазов, яблок и шелка, принадлежащим торговцу. Третья строка содержит три целых неотрицательных числа - стоимости единиц веса алмазов, яблок и шелка соответственно. Последующие строки с 4-ой по **N + 1 **содержат по три целых числа от 0 до 100 включительно, которые соответствуют процентам от стоимости алмазов, яблок и шелку, которые взимаются, соответственно, в городах от 2 до **N - 1 **в качестве налога. В списке городов не учтены родной город торговца 1 и столица N, так как в них с торговца не взимают налог. Последующие M строк содержат по три целых неотрицательных числа, первые два из которых от 1 до N задают пару городов, между которыми проложена дорога, а третье - стоимость проезда по этой дороге. Дороги ведут в направлении от города, указанного первым, до того, который указан вторым. Количества единиц веса каждого из видов товара у торговца, стоимости товаров и цены проезда по дорогам не превышают 100.
Выходные данные
Вывести одно число - точное значение найденной максимальной прибыли от поездки в столицу. Ответ всегда должен содержать ровно два знака после точки. В случаях, когда торговец не может получить прибыль или добраться до столицы по существующим дорогам, требуется вывести 0.00