Выставка «Blobs»
Блобс, известный художник из Цветочного города, планирует провести персональную выставку в местной художественной галерее. Он предложил k картин для показа, но, к сожалению, в галерее есть только n мест для экспонирования. Каждое место представляет собой настенное крепление для картины, и каждое крепление имеет ограничение по весу. Крепление номер i может выдержать картину весом не более d_i граммов. Поскольку невозможно выставить все картины, Блобс оценил художественную ценность a_i каждой из них и взвесил их, чтобы узнать веса w_i (в граммах). Пожалуйста, помогите Блобсу выбрать набор картин для экспонирования, чтобы максимизировать общую художественную ценность.
Напишите программу, которая сопоставит картины с максимальной общей художественной ценностью доступным выставочным местам. Если существует несколько оптимальных решений, любое из них будет считаться правильным.
Входные данные
Первая строка входного файла содержит два целых числа, разделенных пробелом: n и k (1 ≤ n ≤ k ≤ 10000). Вторая строка содержит n целых чисел, разделенных пробелами, которые описывают максимальные нагрузки для креплений: d_1, d_2, d_3, … d_n. Далее следуют k строк, каждая из которых содержит два числа, разделенных пробелом: a_j и w_j, где a_j — художественная ценность, а w_j — вес j-й картины. Картины перечислены в порядке возрастания номеров: третья строка входных данных содержит a_1, w_1, четвертая — a_2, w_2, пятая — a_3, w_3 и так далее (1 ≤ a_i, d_j, w_j ≤ 1000000, 1 ≤ i ≤ n, 1 ≤ j ≤ k).
Выходные данные
Выходной файл должен содержать n целых чисел, разделенных пробелами, представляющих номера картин, которые будут размещены в соответствующих выставочных местах. Число на позиции i — это номер картины, которая будет выставлена в выставочном месте i. Если выставочное место остается пустым, выведите 0 в соответствующей позиции.