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

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ k ≤ 10⁵;

2 ≤ A_i ≤ 10⁵;

1 ≤ B_i ≤ 10⁹;

1 ≤ n ≤ 10⁵;

1 ≤ C_i ≤ 10⁹;

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

2
2 20
2 10
3
10 5 5

Yes
0 1 
1 2 2

1
2 10
1
20

Yes
-1
0