Processing math: 100%

Задача G. Газовые войны

Автор:Южно-Уральский открытый командный чемпионат   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Газовая компания должна поставлять потребителям определенный контрактами объем газа, но при транспортировке газ может откачиваться из трубы и в результате потребители могут не получить газ в нужном объеме.

Напишите программу, вычисляющую минимальный объем газа, который нужно поставлять газовой компании, чтобы всем потребителям газ дошел в объеме, определяемом контрактами.

Формат входного файла

Первая строка входного файла содержит три целых числа, разделенных пробелами — количество потребителей N, количество промежуточных насосных станций K и количество труб для транспортировки газа M.

Вторая строка содержит N целых чисел Vi, разделенных пробелами — объемы газа, которые необходимо поставить потребителям.

Далее следует M строк, содержащих по четыре целых числа, разделенных пробелами — номера узлов aj (0ajK+N) и bj (0bjK+N), связанных трубой, максимальный объем газа fj, который можно подать на вход этой трубы и процент газа dj, который выкачивается из этой трубы при транспортировке.

Узел c номером 0 соответствует компании-поставщику. Потребителям соответствуют узлы с номерами от 1 до N. Промежуточные насосные станции имеют номера от N+1 до N+K. Между двумя узлами проходит не более одной трубы.

Формат выходного файла

В выходной файл вывести одно число — минимальный объем поставок газа для обеспечения всех потребителей с точностью 105. Если для какого-нибудь из потребителей невозможно выполнить поставку в требуемом объеме, то вывести число 1.

Ограничения

1N10,0K100,1M1000,0<Vj100,0<fj100,0dj100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1 3
10
0 1 5 20
0 2 10 5
2 1 10 5
11.21875

0.047s 0.007s 13