N ребят проголодались и решили заказать пиццу. Для этого они хотят выбрать из p предложений от разных продавцов наиболее выгодное. Каждая пицца имеет два размера. Гарантируется, что площадь первой пиццы меньше площади второй. При этом голодающие хотят заказать столько пицц, чтобы каждый получил как минимум m см2 пиццы.
Обратите внимание, что пиццерии иногда проводят акции и готовы привести бесплатно любое количество пицц. В этом случае цена пиццы равна 0.
Входные данные
На первой строке через пробел записаны n - количество ребят, p - количество предложений, m - минимум на одного, затем два числа - площади двух пицц (0
На следующих p строках описаны предложения, где через пробел даны два целых числа a и b цены за данную пиццу первой и второй площади соответственно (0
Выходные данные
Программа должна вывести набор предложений вида:
- номер предложения;
- количество пицц первой площади;
- количество пицц второй площади;
Приоритеты:
1. Выгодность покупки
2. Если существует несколько подходящих по цене предложений, необходимо выбрать предложение с минимальным порядковым номером.
3. Больших пицц должно быть наибольшее количество.
