H. Фондовая биржа
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
16 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Предупреждение: в этой задаче необычное ограничение по памяти!

Боб решил, что он не будет тратить свои лучшие года, создавая программное обеспечение для больших компаний, а вместо этого он будет зарабатывать на хлеб на Рейкьявикской фондовой бирже. Рейкьявикская фондовая биржа — единственная настоящая фондовая биржа в мире. Там есть только один вид транзакций — взять одну акцию вида $$$x$$$ и обменять ее на другую акцию вида $$$y$$$, но это можно сделать, только если цена акции $$$x$$$ не меньше цены акции $$$y$$$.

Всего есть $$$2n$$$ видов акций, пронумерованных от $$$1$$$ до $$$2n$$$, которые интересны Бобу. У Боба есть по одной акции видов от $$$1$$$ до $$$n$$$, а хотел бы в будущем владеть по одной акции видов от $$$n+1$$$ до $$$2n$$$.

Боб смог спрогнозировать цену каждой акции — в момент времени $$$t \geq 0$$$ одна акция вида $$$i$$$ будет стоить $$$a_i \cdot \lfloor t \rfloor + b_i$$$. Сейчас $$$t = 0$$$. Помогите Бобу найти минимально возможный момент времени, когда он сможет владеть по одной акции видов от $$$n+1$$$ до $$$2n$$$ и минимальное количество транзакций, которые нужно совершить, чтобы получить эти акции.

Можете считать, что фондовая биржа имеет неограниченное количество акций каждого вида в любой момент времени.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2200$$$) — количество видов акций, которые есть у Боба.

Каждая из следующих $$$2n$$$ строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$0 \leq a_i, b_i \leq 10^9$$$) — параметры изменения цены $$$i$$$-го вида акций.

Выходные данные

Если Боб не может достичь своей цели, то выведите $$$-1$$$.

Иначе выведите два целых числа $$$T$$$ и $$$E$$$, где $$$T$$$ — минимальное возможное время, когда Боб может достичь своей цели, а $$$E$$$ — минимальное количество транзакций, необходимых для достижения цели в момент времени $$$T$$$.

Примеры
Входные данные
1
3 10
1 16
Выходные данные
3 1
Входные данные
2
3 0
2 1
1 10
1 11
Выходные данные
6 3
Входные данные
1
42 42
47 47
Выходные данные
-1
Входные данные
8
145 1729363
891 4194243
424 853731
869 1883440
843 556108
760 1538373
270 762781
986 2589382
610 99315884
591 95147193
687 99248788
65 95114537
481 99071279
293 98888998
83 99764577
769 96951171
Выходные данные
434847 11
Входные данные
8
261 261639
92 123277
271 131614
320 154417
97 258799
246 17926
117 222490
110 39356
85 62864876
86 62781907
165 62761166
252 62828168
258 62794649
125 62817698
182 62651225
16 62856001
Выходные данные
1010327 11
Примечание

В первом примере Боб может просто ждать, когда будет $$$t = 3$$$ и обе акции будут иметь одинаковую цену, и сделать транзакцию.

Во втором примере оптимальная стратегия выглядит так: нужно обменять акцию вида $$$2$$$ на акцию вида $$$1$$$ в момент времени $$$t = 1$$$, после этого нужно обменять первую акцию вида $$$1$$$ на акцию вида $$$3$$$ в момент времени $$$t = 5$$$ (когда они обе стоят $$$15$$$), а вторую в момент времени $$$t = 6$$$ обменять на акцию вида $$$4$$$ (когда они стоят $$$18$$$ и $$$17$$$ соответственно). Обратите внимание, что он может достичь своей цели за две транзакции, но это он может сделать только в момент времени $$$t = 9$$$, когда он наконец сможет обменять акцию вида $$$2$$$ на акцию вида $$$3$$$.

В третьем примере Боб никогда не сможет достичь своей цели, так как акция второго вида всегда дороже акции первого.