Рабочее место участника

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

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

Первая строка входного файла содержит три целых числа, разделенных пробелами – количество потребителей `N` (`1\ ≤\ N\ ≤\ 10`), количество промежуточных насосных станций `K` (`0\ ≤\ K\ ≤\ 100`) и количество труб для транспортировки газа `M` (`1\ ≤\ M\ ≤\ 1000`). Вторая строка содержит `N` целых чисел `V_i` (`0\ <\ V_j\ ≤\ 100`), разделенных пробелами – объемы газа, которые необходимо поставить потребителям. Далее следует `M` строк, содержащих по четыре целых числа, разделенных пробелами – номера узлов `a_j` (`0\ ≤\ a_j\ ≤\ K+N`) и `b_j` (`0\ ≤\ b_j\ ≤\ K+N`), связанных трубой, максимальный объем газа `f_j` (`0\ <\ f_j\ ≤\ 100`), который можно подать на вход этой трубы и процент газа `d_j` (`0\ ≤\ d_j\ ≤\ 100`), который выкачивается из этой трубы при транспортировке. Узел c номером 0 соответствует компании-поставщику. Потребителям соответствуют узлы с номерами от 1 до `N`. Промежуточные насосные станции имеют номера от `N+1` до `N+K`. Между двумя узлами проходит не более одной трубы.

В выходной файл вывести одно число – минимальный объем поставок газа для обеспечения всех потребителей с точностью `10^{-5}`. Если для какого-нибудь из потребителей невозможно выполнить поставку в требуемом объеме, то вывести число `-1`.

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

11.21875