Виставка «Блобс»
Blobs, відомий художник з Квіткового Міста, планує провести персональну виставку в місцевій художній галереї. Він подав k робіт для експонування, але, на жаль, галерея має лише n місць для експозиції. Кожне місце для експозиції — це настінний тримач для картин. Під час підготовки з'ясувалося, що тримачі розраховані на картини різної ваги. Тримач номер i може витримати експонат вагою не більше ніж d_i грамів. Оскільки неможливо виставити всі роботи, Blobs оцінив художню цінність a_i кожної картини. Він також зважив їх усі, щоб знати вагу w_i (у грамах). Допоможіть Blobs вибрати набір картин для експозиції, максимізуючи загальну художню цінність.
Напишіть програму, яка визначить набір картин з максимальною загальною художньою цінністю, що відповідає доступним місцям для експозиції. Якщо існує кілька оптимальних рішень, будь-яке з них буде прийняте як правильне.
Вхідні дані
Перша строка вхідного файлу містить два цілі числа, розділені пробілом: n і k (1 ≤ n ≤ k ≤ 10000). Друга строка містить n цілих чисел, розділених пробілом, що описують максимальні навантаження для тримачів: d_1, d_2, d_3, … d_n. Далі йдуть k строк, кожна з яких містить два числа, розділені пробілом: 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 у відповідній позиції.