21700번 - Сочи-2014 스페셜 저지다국어

К предстоящей олимпиаде в Сочи требуется возвести N олимпийских объектов. Процесс строительства каждого объекта определяется освоением выделяемых на него денежных средств.

В строительстве объектов готовы участвовать K фирм. Фирмы имеют разные строительные мощности, выраженные в количестве денежных средств, которые фирма может осваивать в единицу времени.

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

Администрация строительства олимпийских объектов заинтересована в скорейшем освоении денежных средств, поэтому хочет составить такой график работ, при следовании которому строительство будет завершено в кратчайшие сроки. В графике будет указано время, в течение которого тот или иной объект будет строиться какой-то фирмой. 

Напишите программу, результаты работы которой позволят администрации построить требуемый график. 

Первая строка входного файла содержит целое число N — количество объектов (1 ≤ N ≤ 50). Во второй строке содержатся разделенные пробелами целочисленные значения S₁, S₂, S₃, …, S_N объемов денежных средств, выделяемых для строительства каждого из объектов. Числа S_i выражены в тысячах рублей, положительные и не превышают 1000.

В третьей строке находится целое число K — количество строительных фирм (1 ≤ K ≤ 50). Четвертая строка содержит разделенные пробелами целочисленные значения мощностей каждой из фирм V₁, V₂, V₃, …, V_K в тыс.руб/час. Числа V_j положительные и не превышают 1000.

Первая строка выходного файла содержит действительное число T — время в часах окончания всех работ, считая с начала строительства, выведенное не менее чем с тремя точными знаками после запятой. Далее в каждой строке выходного файла содержатся разделенные пробелами три числа: t, i, j, где действительное число t — время от начала строительства в часах, в которое j-я фирма приступает к строительным работам на i-м объекте.

Значения времен необходимо выводить с максимально возможной точностью.

Строки должны быть отсортированы по неубыванию t.