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

Память фотоаппарата составляет d мегабайт. Фотоаппарат Валеры умеет делать фотографии в высоком и низком качестве. Одна фотография в низком качестве занимает a мегабайт памяти, одна фотография в высоком качестве занимает b мегабайт памяти. По необъяснимым причинам каждый клиент просит сделать ему несколько фотографий в низком и несколько фотографий в высоком качестве. Более формально, i-ый клиент приходит с просьбой сделать ему x_i фотографий в низком качестве и y_i фотографий в высоком качестве.

Валера хочет обслужить как можно больше клиентов, чтобы они остались довольны его работой. Чтобы i-ый клиент остался доволен работой Валеры, ему нужно выполнить заказ клиента полностью, то есть сделать x_i фотографий в низком качестве и y_i фотографий в высоком качестве. Чтобы сделать одну фотографию в низком качестве, в памяти фотоаппарата должно быть не менее a мегабайт свободной памяти. Аналогично чтобы сделать одну фотографию в высоком качестве, в памяти фотоаппарата должно быть не менее b мегабайт свободной памяти. Изначально память фотоаппарата пуста. Также Валера не удаляет фотографии из фотоаппарата, поэтому память фотоаппарата постепенно заполняется.

Посчитайте, какое максимальное количество клиентов Валера сможет успешно обслужить, а также выведите номера этих клиентов.