Осада
시간 제한2초메모리 제한256 MB
방어군이 A의 마나로 유물 일부를 활성화하고 공격군이 B의 마나로 최대한 많은 유물을 파괴할 때, 살아남는 유물 수를 최대로 만드는 활성화 집합을 찾는다.
문제
Для славного города Альдерсберг настали тяжелые времена. С минуты на минуту несметные полчища врагов пойдут на штурм. Только магические барьеры могут помочь удержать город.
В арсенале защитников города имеется n артефактов, позволяющих поставить барьер. Для активации i-го артефакта требуется ai мерлинов (единиц магической энергии). После этого, используя bi мерлинов, противник может разрушить артефакт на расстоянии.
Защитники города располагают A мерлинами магической энергии, в арсенале противника B мерлинов. Запасы магической энергии не восполняются. Горожане решили активировать артефакты так, чтобы после их разрушения магами противника, максимальное число осталось активно.
Помогите защитникам города выбрать, какие артефакты нужно активировать.
입력
Первая строка содержит три целых числа A, B и n (0 ≤ A, B ≤ 105, 0 ≤ n ≤ 1000), разделенных пробелами. Следующие n строк содержат пары чисел ai и bi (1 ≤ ai, bi ≤ 105).
출력
В первой строке выведите число артефактов, которые останутся активны при оптимальных действиях обеих сторон конфликта. Во второй строке выведите число артефактов, которые должны активировать защитники города, и номера этих артефактов. Числа в одной строке разделяйте пробелами. Артефакты занумерованы, начиная с единицы, в порядке, в котором они заданы во вводе.