Задача D. Электричество

Автор:Жюри ВКОШП-2009   Ограничение времени:2 сек
Входной файл:electro.in   Ограничение памяти:256 Мб
Выходной файл:electro.out  

Условие

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

Было закуплено n устройств: системные блоки, мониторы, проектор и т. д. Однако, когда начался процесс подключения, неожиданно выяснилось, что в кабинете есть только одна электрическая розетка.

Решение было найдено достаточно быстро — были куплены k сетевых фильтров. После этого выяснилось, что как устройства, так и сетевые фильтры обладают различными характеристиками — это делает процесс подключения нетривиальным. Для каждого сетевого фильтра известно число Ai розеток в нем и максимальная суммарная мощность Bi устройств, которые могут быть в него подключены, а для каждого устройства известна потребляемая им мощность Ci.

Теперь необходимо составить схему подключения устройств с использованием сетевых фильтров такую, что суммарная мощность устройств, включенных в каждый сетевой фильтр (как напрямую, так и через другие сетевые фильтры) не превосходит соответствующего значения Bi, а число устройств и других сетевых фильтров, напрямую включенных в этот, не превосходит Ai. При этом, в соответствии с правилами пожарной безопасности, в каждый сетевой фильтр можно подключать не более одного другого сетевого фильтра.

Можно считать, что единственная в классе розетка рассчитана на достаточно большую мощность — она выдержит подключение всех имеющихся устройств. Отметим также, что при необходимости в розетку можно включить не сетевой фильтр, а устройство напрямую.

Напишите программу, которая найдет требуемую схему подключения устройств.

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

Первая строка входного файла содержит k — число имеющихся в наличии сетевых фильтров. Далее следуют k строк, описывающих эти сетевые фильтры: каждая из них содержит по два целых числа: Ai и Bi — количество розеток в нем и максимальную суммарную мощность приборов, которые можно включить в него, соответственно.

Следующая строка содержит n — число приборов, которые нужно подключить. Последняя строка входного файла содержит мощности этих приборов: C1, …, Cn.

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

В выходной файл выведите слово Yes, если все приборы можно подключить с использованием имеющихся в наличии сетевых фильтров, и слово No — в противном случае.

Если ответ на задачу положительный, то далее выведите описание схемы подключения. Оно должно состоять из двух строк. Первая из этих строк должна описывать подключение сетевых фильтров: для каждого из них выведите номер фильтра, в который он подключен~(если он подключен в единственную розетку в классе, то выведите число 0, а если он вообще не используется, то число 1). Вторая из этих строк должна описывать подключение приборов: для каждого из приборов выведите номер сетевого фильтра~(если прибор следует подключить непосредственно в розетку, то выведите число 0), в который он подключен.

Учитывайте, что в каждый сетевой фильтр может быть подключен не более чем один другой сетевой фильтр, а подключать фильтр сам к себе не разрешается. Если в сетевой фильтр не включены (напрямую или через другие сетевые фильтры) никакие устройства, то он также не должен быть никуда включен. Кроме этого, если фильтр не включен~(напрямую или через другие сетевые фильтры) в розетку, то он также не должен быть никуда включен.

Сетевые фильтры нумеруются, начиная с единицы, в порядке их перечисления во входном файле. Порядок вывода описания подключения фильтров и приборов должен совпадать с порядком их перечисления во входном файле.

Ограничения

1 ≤ k ≤ 105;

2 ≤ Ai ≤ 105;

1 ≤ Bi ≤ 109;

1 ≤ n ≤ 105;

1 ≤ Ci ≤ 109;

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

Входной файл (electro.in) Выходной файл (electro.out)
1
2
2 20
2 10
3
10 5 5
Yes
0 1 
1 2 2
2
1
2 10
1
20
Yes
-1
0

0.049s 0.016s 15