Валера давно мечтал работать фотографом, и поэтому купил себе новый фотоаппарат. С каждым днем он получал все больше и больше заказов на фотографии, и в один прекрасный день Валере понадобилась программа, которая будет определять, сколько максимум человек он сможет обслужить.
Память фотоаппарата составляет d мегабайт. Фотоаппарат Валеры умеет делать фотографии в высоком и низком качестве. Одна фотография в низком качестве занимает a мегабайт памяти, одна фотография в высоком качестве занимает b мегабайт памяти. По необъяснимым причинам каждый клиент просит сделать ему несколько фотографий в низком и несколько фотографий в высоком качестве. Более формально, i-ый клиент приходит с просьбой сделать ему xi фотографий в низком качестве и yi фотографий в высоком качестве.
Валера хочет обслужить как можно больше клиентов, чтобы они остались довольны его работой. Чтобы i-ый клиент остался доволен работой Валеры, ему нужно выполнить заказ клиента полностью, то есть сделать xi фотографий в низком качестве и yi фотографий в высоком качестве. Чтобы сделать одну фотографию в низком качестве, в памяти фотоаппарата должно быть не менее a мегабайт свободной памяти. Аналогично чтобы сделать одну фотографию в высоком качестве, в памяти фотоаппарата должно быть не менее b мегабайт свободной памяти. Изначально память фотоаппарата пуста. Также Валера не удаляет фотографии из фотоаппарата, поэтому память фотоаппарата постепенно заполняется.
Посчитайте, какое максимальное количество клиентов Валера сможет успешно обслужить, а также выведите номера этих клиентов.
Выходные данные
В первую строку выведите ответ на задачу — максимальное количество клиентов, которое Валера сможет успешно обслужить. Во вторую строку выведите номера этих клиентов в произвольном порядке. Все номера должны быть различны. Если ответов несколько, выведите любой из них. Клиенты нумеруются, начиная с 1, в том порядке, в котором они заданы во входных данных.