Blobs, a renowned painter from Flower Town is
about to have a solo show at the local art gallery. He presented k
works 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 di grams. As it is impossible to display
all the works anyway, Blobs estimated the artistic value ai
of each painting. He also weighted all of them to know the weights wi
(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.
Limitations
All numbers are integer.
1 ≤ n ≤ k
≤ 10 000; 1 ≤ di, aj,
wj ≤ 1 000 000; 1 ≤ i
≤ n; 1 ≤ j ≤ k.
Input
The first line of the input file contains
two space-delimited integers n and k. The second
line contains n space-delimited integers describing maximum loads
for holders: d1, d2, d3,
… dn. Then k lines follow, with two
space-delimited numbers each: aj and wj,
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 a1, w1, the fourth –
a2, w2, the fifth – a3,
w3, and so on.
Output
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.
Example
Input
|
Output
|
|
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 1 8
10
|
