시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB0000.000%

문제

Для славного города Альдерсберг настали тяжелые времена. С минуты на минуту несметные полчища врагов пойдут на штурм. Только магические барьеры могут помочь удержать город.

В арсенале защитников города имеется n артефактов, позволяющих поставить барьер. Для активации i-го артефакта требуется ai мерлинов (единиц магической энергии). После этого, используя bi мерлинов, противник может разрушить артефакт на расстоянии.

Защитники города располагают A мерлинами магической энергии, в арсенале противника B мерлинов. Запасы магической энергии не восполняются. Горожане решили активировать артефакты так, чтобы после их разрушения магами противника, максимальное число осталось активно.

Помогите защитникам города выбрать, какие артефакты нужно активировать.

입력

Первая строка содержит три целых числа AB и n (0 ≤ AB ≤ 105, 0 ≤ n ≤ 1000), разделенных пробелами. Следующие n строк содержат пары чисел ai и bi (1 ≤ aibi ≤ 105).

출력

В первой строке выведите число артефактов, которые останутся активны при оптимальных действиях обеих сторон конфликта. Во второй строке выведите число артефактов, которые должны активировать защитники города, и номера этих артефактов. Числа в одной строке разделяйте пробелами. Артефакты занумерованы, начиная с единицы, в порядке, в котором они заданы во вводе.

예제 입력 1

1 1 2
1 1
1 2

예제 출력 1

1
1 2