Уже совсем скоро состоится крупнейшее в мире соревнование по программированию, а в тестирующей системе до сих пор имеется m багов. У организатора соревнования — одного известного университета — нет иного выбора, как привлечь студентов университета к исправлению всех багов. В университете учатся n студентов, способных выполнять такую работу. Студенты понимают, что являются единственной надеждой организаторов, поэтому не готовы работать бесплатно: i-ый студент за свою помощь хочет получить ci зачетов (независимо от объема проделанной им работы).
Как баги, так и студенты, не одинаковые: каждый баг характеризуется сложностью aj, а каждый студент — уровнем своих способностей bi. Студент i способен пофиксить баг j лишь в том случае, если уровень его способностей не меньше сложности бага: bi ≥ aj, причем он делает это за один день. В противном случае для исправления этого бага придется использовать какого-либо другого студента. Разумеется, никакой студент не может работать над несколькими багами в течение одного дня. Все баги не зависят друг от друга, поэтому их можно исправлять в любом порядке, а разные студенты могут работать параллельно.
Университет хочет исправить все баги как можно быстрее, при этом выставив студентам суммарно не более s зачетов. Определите, каких студентов нужно для этого привлечь, а также расписание работ: какой студент должен исправлять какой баг.
Выходные данные
Если все баги исправить не удастся, выведите «NO».
Иначе в первой строке выведите «YES», а затем выведите m целых чисел через пробел: i-ое из этих чисел должно равняться номеру студента, который исправит i-ый баг в оптимальном ответе. Баги должны быть исправлены как можно быстрее (должно быть потрачено наименьшее количество дней), а суммарное количество выставленных зачетов не должно при этом превышать s. Если существует несколько оптимальных ответов, разрешается вывести любой.
Примечание
Рассмотрим первый пример.
Третий студент (с уровнем способностей 3) должен исправлять второй и четвертый баги (сложностей 3 и 2 соответственно), а второй студент (с уровнем способностей 1) — первый и третий баги (их сложность также равна 1). Исправление каждого бага займет у каждого студента один день, поэтому на исправление всех багов потребуется два дня (студенты могут работать параллельно).
Второй студент требует за свою помощь 3 зачета, а третий — 6. Это укладывается в возможности университета, который готов поставить не более 9 зачетов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 9
1 3 1 2
2 1 3
4 3 6
|
YES
2 3 2 3
|
|
2
|
3 4 10
2 3 1 2
2 1 3
4 3 6
|
YES
1 3 1 3
|
|
3
|
3 4 9
2 3 1 2
2 1 3
4 3 6
|
YES
3 3 2 3
|
|
4
|
3 4 5
1 3 1 2
2 1 3
5 3 6
|
NO
|