АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1255. Blobs' Exhibition

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

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 ≤ nk ≤ 10 000; 1 ≤ di, aj, wj ≤ 1 000 000; 1 ≤ in; 1 ≤ jk.

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

 

All Rybinsk-2013 problems

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Чемпионат ACM / Рыбинск-2013 /
1254. C - Plunder & Flee 1255. 1256. E - Number Game 1257. F - Evil & Odious 1258. G - Checkers
 
время генерации 0.093 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.