Задача №111906. Выставка
Известный художник Блобс устраивает выставку своих работ в местной картинной галерее. Он хочет представить на выставке k своих работ, но в галерее есть всего лишь n держателей для картин. Во время подготовки выяснилось, что держатели рассчитаны на картины разного веса. На держатель c номером i может быть установлена картина весом не более d i граммов. По этим причинам может случится так, что не удастся выставить все картины. В связи с этим обстоятельством Блобс определил для каждой картины два значения: красоту — a i и вес в граммах — w i . Помогите Блобсу выбрать множество картин для выставки, так чтобы максимизировать суммарную красоту всех выставленных картин.
Напишите программу, которая найдет требуемое множество картин. Если оптимальных ответов несколько, разрешается вывести любой.
Все числа во входном файле целые. 1 ≤ n ≤ k ≤ 10 000 ; 1 ≤ d i , a j , w j ≤ 1 000 000 ; 1 ≤ i ≤ n ; 1 ≤ j ≤ k .
В первой строке входного файла содержатся два числа разделенных пробелом — n и k . Вторая строка содержит n разделенных пробелом чисел — d 1 , d 2 , ... d n . В следующих k строках по два числа — a j и w j .
Выведите n чисел, i -e из которых обозначает номер картины, выставленной на i -ом держателе. Если держатель пуст выведите 0 на соответствующей позиции. Картины должны быть занумерованы в том порядке, в котором они встречаются во входном файле.
5 10 1 2 3 4 5 10 3 4 3 11 8 1 5 5 8 7 1 5 5 8 3 4 2 7 3
6 9 8 1 10