Мэр города Урюпинска решил посадить на главной аллее города, которая проходит с запада на восток, голубые ели. Причем сажать ели можно не во всех местах, а только на специально оставленных при асфальтировании аллеи клумбах.
Как оказалось, голубые ели бывают M различных сортов. Для ели каждого сорта известна максимальная длина ее тени в течение дня в западном и в восточном направлении (W
i и E
i соответственно). При этом известно, что ели растут гораздо лучше, если в течение дня они не оказываются в тени других елей.
Координатная ось направлена вдоль аллеи с запада на восток.
По заданным координатам клумб вычислите максимальное число елей, которое можно посадить, соблюдая условие о том, что никакая ель не должна попадать в тень от другой ели.
Входные данные
Во входном файле записано сначала натуральное число M — количество сортов елей (1<M<100). Затем идет M пар чисел W
i, E
i, описывающих максимальную длину тени в западном и восточном направлении в течение дня для каждого сорта ели (числа W
i, E
i — целые, из диапазона от 0 до 30000). Далее идет натуральное число N — количество клумб, в которых можно сажать ели (1<N<100). Далее идет N чисел, задающих координаты клумб (координаты — целые числа, по модулю не превышающие 30000). Клумбы перечислены с запада на восток (в порядке возрастания их координат).
Примечание
Если на клумбе с координатой X мы посадили ель, максимальная тень которой в восточном направлении равна E, то все клумбы с координатами от X+1 до X+E–1 попадают в тень от этой ели, а клумба с координатами X+E — уже нет. Аналогично для тени в западном направлении.
Выходные данные
В выходной файл выведите сначала число A — максимальное количество елей, которые удастся посадить, а затем A пар чисел, описывающих ели. Первое число каждой пары задает номер клумбы, в которую садится ель. Второе число определяет номер сорта этой ели.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
10 1
2 2
1 10
10
0
1
3
5
7
9
11
13
15
16
|
8
9 2
8 2
7 2
6 2
5 2
4 2
3 2
1 2
|