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

Условие

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

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

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

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

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

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

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

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

Ограничения

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

1 1 3
10
0 1 5 20
0 2 10 5
2 1 10 5

11.21875