Московская городская олимпиада школьников по информатике,
2003/04 учебный год
при поддержке компаний
Задача E. Еловая аллея
| Имя входного файла: | e.in |
| Имя выходного файла: | e.out |
| Максимальное время работы на одном тесте: | 3 секунды |
| Максимальный объем используемой памяти: | 8 мегабайт |
Мэр города Урюпинска решил посадить на главной аллее города, которая проходит с запада на восток, голубые ели. Причем сажать ели можно не во всех местах, а только на специально оставленных при асфальтировании аллеи клумбах.
Как оказалось, голубые ели бывают M различных сортов. Для ели каждого сорта известна максимальная длина ее тени в течение дня в западном и в восточном направлении (Wi и Ei соответственно). При этом известно, что ели растут гораздо лучше, если в течение дня они не оказываются в тени других елей.
Координатная ось направлена вдоль аллеи с запада на восток.
По заданным координатам клумб вычислите максимальное число елей, которое можно посадить, соблюдая условие о том, что никакая ель не должна попадать в тень от другой ели.
Формат входных данных
Во входном файле записано сначала натуральное число M - количество сортов елей (1≤M≤100). Затем идет M пар чисел Wi, Ei, описывающих максимальную длину тени в западном и восточном направлении в течение дня для каждого сорта ели (числа Wi, Ei - целые, из диапазона от 0 до 30000). Далее идет натуральное число N - количество клумб, в которых можно сажать ели (1≤N≤100). Далее идет N чисел, задающих координаты клумб (координаты - целые числа, по модулю не превышающие 30000). Клумбы перечислены с запада на восток (в порядке возрастания их координат).
Примечание
Если на клумбе с координатой X мы посадили ель, максимальная тень которой в восточном направлении равна E, то все клумбы с координатами от X+1 до X+E-1 попадают в тень от этой ели, а клумба с координатами X+E - уже нет. Аналогично для тени в западном направлении.
Формат выходных данных
В выходной файл выведите сначала число A - максимальное количество елей, которые удастся посадить, а затем A пар чисел, описывающих ели. Первое число каждой пары задает номер клумбы, в которую садится ель. Второе число определяет номер сорта этой ели.
Пример
| e.in | e.out |
3 1000 3 1 200 128 256 3 1 2 4 |
2 1 1 3 2 |