H. Очередь в кассы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На почту пришли $$$n$$$ посетителей, $$$i$$$-й из них хочет сделать $$$a_i$$$ дел. Все $$$n$$$ посетителей стоят в одной очереди друг за другом. Первый посетитель, стоящий в очереди, имеет номер $$$1$$$, посетитель, стоящий за ним, имеет номер $$$2$$$, и так далее.

На почте есть $$$m$$$ касс, в каждой из которых сидит ровно по одному кассиру. Обслуживание $$$i$$$-го посетителя в кассе проходит следующим образом. Сначала проходит $$$x_j$$$ секунд, в течение которых кассир знакомится с посетителем. После этого каждое из дел посетителя будет выполнено кассиром за $$$y_j$$$ секунд. Посетитель не покинет кассу, пока не сделает все свои $$$a_i$$$ дел. Таким образом, на обслуживание $$$i$$$-го посетителя в $$$j$$$-й кассе потребуется $$$x_j + y_j \cdot a_i$$$ секунд.

В каждый момент времени человек, стоящий первым в очереди, идёт в свободную кассу, если таковая имеется. Если таких касс несколько, то он выбирает кассу с минимальным номером. Если в один момент времени есть более одной кассы и более одного человека в очереди, считайте, что они подходят к кассам одновременно, но выбор кассы в первую очередь осуществляет тот, кто раньше стоит в очереди. Изначально все кассы свободны.

Перед вами стоит задача промоделировать описанный процесс и вывести время, по истечении которого будут обслужены все посетители. Также определите номера касс, которыми будут пользоваться посетители.

Входные данные

В первой строке следуют два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^{5}$$$) — количество посетителей и количество касс.

Во второй строке следует $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$), где $$$a_i$$$ равно количеству дел $$$i$$$-го посетителя.

В следующих $$$m$$$ строках следует по два целых числа $$$x_j$$$ и $$$y_j$$$ ($$$1 \le x_j, y_j \le 100$$$) — время, которое нужно $$$j$$$-му кассиру на знакомство с посетителем, а также время, которое он тратит на выполнение одного дела посетителя.

Выходные данные

В первую строку выведите время, по истечении которого будут обслужены все посетители.

Во вторую строку выведите $$$n$$$ чисел, где $$$i$$$-е число должно быть равно номеру кассы, в которой будет обслуживаться $$$i$$$-й посетитель.

Примеры
Входные данные
3 3
1 2 3
3 4
3 2
2 1
Выходные данные
7
1 2 3
Входные данные
5 1
4 3 2 4 6
5 3
Выходные данные
82
1 1 1 1 1
Примечание

В первом примере $$$3$$$ посетителя и $$$3$$$ свободные кассы. Первый посетитель сразу же пойдёт в первую кассу и будет обслужен через $$$3 + 4 \cdot 1 = 7$$$ секунд, второй посетитель — во вторую кассу и будет обслужен через $$$3 + 2 \cdot 2 = 7$$$ секунд, а третий посетитель — в третью кассу и будет обслужен через $$$2 + 1 \cdot 3 = 6$$$ секунд. Таким образом, все посетители будут обслужены через $$$7$$$ секунд.

Во втором примере всего одна касса, поэтому все посетители будут обслужены в ней по очереди. Суммарно на это уйдет $$$82$$$ секунды.