| Автор: | Жюри всероссийской олимпиады школьников 2008 | Ограничение времени: | 2 сек | |
| Входной файл: | olymp.in | Ограничение памяти: | 64 Мб | |
| Выходной файл: | olymp.out | |||
| Максимальный балл: | 100 |
К предстоящей олимпиаде в Сочи требуется возвести N олимпийских объектов. Процесс строительства каждого объекта определяется освоением выделяемых на него денежных средств.
В строительстве объектов готовы участвовать K фирм. Фирмы имеют разные строительные мощности, выраженные в количестве денежных средств, которые фирма может осваивать в единицу времени.
В каждый момент времени фирма может осуществлять работы только на одном объекте. В строительстве одного объекта не могут одновременно участвовать несколько фирм. В любой момент времени любой объект может быть передан для продолжения строительства любой фирме.
Администрация строительства олимпийских объектов заинтересована в скорейшем освоении денежных средств, поэтому хочет составить такой график работ, при следовании которому строительство будет завершено в кратчайшие сроки. В графике будет указано время, в течение которого тот или иной объект будет строиться какой-то фирмой.
Напишите программу, результаты работы которой позволят администрации построить требуемый график.
Первая строка входного файла содержит целое число N - количество объектов. Во второй строке содержатся разделенные пробелами целочисленные значения S1, S2, S3, …, SN объемов денежных средств, выделяемых для строительства каждого из объектов.
В третьей строке находится целое число K — количество строительных фирм. Четвертая строка содержит разделенные пробелами целочисленные значения мощностей каждой из фирм V1, V2, V3, …, VK в тыс.руб/час.
Первая строка выходного файла содержит действительное число T — время в часах окончания всех работ, считая с начала строительства, выведенное не менее чем с тремя точными знаками после запятой. Далее в каждой строке выходного файла содержатся разделенные пробелами три числа: t, i, j, где действительное число t - время от начала строительства в часах, в которое j-я фирма приступает к строительным работам на i-м объекте.
Значения времен необходимо выводить с максимально возможной точностью.
Строки должны быть отсортированы по неубыванию t.
1 ≤ N ≤ 50
1 ≤ K ≤ 50
Числа Si выражены в тысячах рублей, положительные и не превышают 1000.
Числа Vj положительные и не превышают 1000.
| № | Входной файл (olymp.in) |
Выходной файл (olymp.out) |
|---|---|---|
| 1 | |
|
| 2 | |
|