eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Blobs` Exhibition

Blobs` Exhibition

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Blobs, a renowned painter from Flower Town is about to have a solo show at the local art gallery. He presented kworks to be exhibited but unfortunately the gallery has only n exhibit spaces. Each exhibit space is a wall-mounted painting holder. During preparations it turned out that the holders are designed for paintings of different weight. Holder number i can carry an exhibit weighting no more than d_i grams. As it is impossible to display all the works anyway, Blobs estimated the artistic value a_i of each painting. He also weighted all of them to know the weights w_i (in grams). Please help Blobs in selecting a set of paintings to be displayed, maximizing the total artistic value.

Write a program that will map the set of paintings having the maximum total artistic value to the available exhibit spaces. If several optimal solutions exist, any of them will be accepted as correct.

Вхідні дані

The first line of the input file contains two space-delimited integers n and k (1nk10000). The second line contains n space-delimited integers describing maximum loads for holders: d_1, d_2, d_3, … d_n. Then k lines follow, with two space-delimited numbers each: a_j and w_j, the artistic value and the weight of the j-th painting. The paintings are listed in ascending order of numbers: the third line of input contains a_1, w_1, the fourth – a_2, w_2, the fifth – a_3, w_3, and so on (1a_i, d_j, w_j1000000, 1in, 1jk).

Вихідні дані

The output file should contain n integers separated with spaces — the numbers of paintings to be placed in corresponding exhibit spaces. Here, the number in position i is the number of painting to be displayed in the exhibit space i. If an exhibit space is empty then output 0 in the corresponding position.

Приклад

Вхідні дані #1
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
Вихідні дані #1
6 9 1 8 10
Джерело 2013-2014 ACM Central Region of Russia Quarterfinal, Rybinsk 2013/10/17