Виставка «Блобс»#6189

Виставка «Блобс»

1 секунда

64 мегабайти

Дуже легка

Блобс, відомий художник з Квіткового Міста, планує провести персональну виставку в місцевій художній галереї. Він подав $k$ робіт для експонування, але, на жаль, галерея має лише $n$ місць для експозиції. Кожне місце для експозиції — це настінний тримач для картин. Під час підготовки з'ясувалося, що тримачі розраховані на картини різної ваги. Тримач номер $i$ може витримати експонат вагою не більше ніж $d_{i}$ d_i грамів. Оскільки неможливо виставити всі роботи, Блобс оцінив художню цінність $a_{i}$ a_i кожної картини. Він також зважив їх усі, щоб знати вагу $w_{i}$ w_i (у грамах). Допоможіть Блобсу вибрати набір картин для експозиції, максимізуючи загальну художню цінність.

Напишіть програму, яка визначить набір картин з максимальною загальною художньою цінністю, що відповідає доступним місцям для експозиції. Якщо існує кілька оптимальних рішень, будь-яке з них буде прийняте як правильне.

Вхідні дані

Перший рядок вхідного файлу містить два цілі числа, розділені пробілом: $n$ і $k$ ( $1 \leq n \leq k \leq 10000$ 1 \le n \le k \le 10000). Другий рядок містить $n$ цілих чисел, розділених пробілом, що описують максимальні навантаження для тримачів: $d_{1}$ d_1, $d_{2}$ d_2, $d_{3}$ d_3, … $d_{n}$ d_n. Далі йдуть $k$ рядків, кожен з яких містить два числа, розділені пробілом: $a_{j}$ a_j і $w_{j}$ w_j, художню цінність та вагу $j$ -ї картини. Картини перераховані у порядку зростання номерів: третій рядок вхідних даних містить $a_{1}$ a_1, $w_{1}$ w_1, четвертий — $a_{2}$ a_2, $w_{2}$ w_2, п'ятий — $a_{3}$ a_3, $w_{3}$ w_3 і так далі ( $1 \leq a_{i}, d_{j}, w_{j} \leq 1000000$ 1 \le a_i, d_j, w_j \le 1000000, $1 \leq i \leq n$ 1 \le i \le n, $1 \leq j \leq k$ 1 \le j \le k).

Вихідні дані

Вихідний файл повинен містити $n$ цілих чисел, розділених пробілами — номери картин, які слід розмістити у відповідних місцях для експозиції. Тут число на позиції $i$ — це номер картини, яку слід виставити у місці для експозиції $i$ . Якщо місце для експозиції порожнє, виведіть $0$ у відповідній позиції.

Приклади

Приклад 1