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

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10, 0 ≤ K ≤ 100, 1 ≤ M ≤ 1000, 0 < Vj ≤ 100, 0 < fj ≤ 100, 0 ≤ dj ≤ 100

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

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

0.085s 0.012s 13