Задача №112142. Еловая аллея
Мэр города Урюпинска решил посадить на главной аллее города, которая проходит с запада на восток, голубые ели. Причем сажать ели можно не во всех местах, а только на специально оставленных при асфальтировании аллеи клумбах.
Как оказалось, голубые ели бывают M различных сортов. Для ели каждого сорта известна максимальная длина ее тени в течение дня в западном и в восточном направлении ( W i и E i соответственно). При этом известно, что ели растут гораздо лучше, если в течение дня они не оказываются в тени других елей.
Координатная ось направлена вдоль аллеи с запада на восток.
По заданным координатам клумб вычислите максимальное число елей, которое можно посадить, соблюдая условие о том, что никакая ель не должна попадать в тень от другой ели.
Во входном файле записано сначала натуральное число M — количество сортов елей. Затем идет M пар целых чисел W i , E i , описывающих максимальную длину тени в западном и восточном направлении в течение дня для каждого сорта ели. Далее идет натуральное число N — количество клумб, в которых можно сажать ели. Далее идет N целых чисел P i , задающих координаты клумб. Клумбы перечислены с запада на восток (в порядке возрастания их координат).
В выходной файл выведите сначала число A — максимальное количество елей, которые удастся посадить, а затем A пар чисел, описывающих ели. Первое число каждой пары задает номер клумбы, в которую садится ель. Второе число определяет номер сорта этой ели.
Если на клумбе с координатой X мы посадили ель, максимальная тень которой в восточном направлении равна E , то все клумбы с координатами от X + 1 до X + E –1 попадают в тень от этой ели, а клумба с координатами X + E — уже нет. Аналогично для тени в западном направлении.
Оценивание:
Первая группа тестов ( 1 - 13 тесты, 30 баллов) состоит из тестов, для которых выполняются ограничения 1 ≤ N , M ≤ 100 , 0 ≤ W i , E i ≤ 30000 , - 30000 ≤ P i ≤ 30000 .
Вторая группа тестов ( 14 - 28 тесты, 30 баллов) состоит из тестов, для которых выполняются ограничения 1 ≤ N , M ≤ 500 , 0 ≤ W i , E i ≤ 10 8 , - 10 8 ≤ P i ≤ 10 8 .
Третья группа тестов ( 29 - 44 тесты, 40 баллов) состоит из тестов, для которых выполняются ограничения 1 ≤ N , M ≤ 2000 , 0 ≤ W i , E i ≤ 10 8 , - 10 8 ≤ P i ≤ 10 8 .
Баллы за группы начисляются только при прохождении всех тестов данной группы, а также всех тестов предыдущих групп.
3 1000 3 1 200 128 256 3 1 2 4
2 1 1 3 2