CF1178H.Stock Exchange

Warning: This problem has an unusual memory limit!

Bob decided that he will not waste his prime years implementing GUI forms for a large corporation and instead will earn his supper on the Stock Exchange Reykjavik. The Stock Exchange Reykjavik is the only actual stock exchange in the world. The only type of transaction is to take a single share of stock $x$ and exchange it for a single share of stock $y$, provided that the current price of share $x$ is at least the current price of share $y$.

There are $2n$ stocks listed on the SER that are of interest to Bob, numbered from $1$ to $2n$. Bob owns a single share of stocks $1$ through $n$ and would like to own a single share of each of $n+1$ through $2n$ some time in the future.

Bob managed to forecast the price of each stock — in time $t \geq 0$, the stock $i$ will cost $a_i \cdot \lfloor t \rfloor + b_i$. The time is currently $t = 0$. Help Bob find the earliest moment in time in which he can own a single share of each of $n+1$ through $2n$, and the minimum number of stock exchanges he has to perform in order to do that.

You may assume that the Stock Exchange has an unlimited amount of each stock at any point in time.

警告：本题具有特殊的内存限制！

鲍勃决定不将自己宝贵的青春年华浪费在为一家大型企业实现 GUI 表单上，而是转战雷克雅未克证券交易所（SER）谋生。雷克雅未克证券交易所是世界上唯一真正存在的证券交易所。其唯一允许的交易类型是：用一股股票 $x$ 换取一股股票 $y$，前提是当前股票 $x$ 的价格不低于股票 $y$ 的价格。

SER 上共有 $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$ 各一股，并求出达成该目标所需的最少股票交换次数。

你可以假设：在任意时刻，证券交易所对每种股票均有无限供应。

The first line contains a single integer $n$ ($1 \leq n \leq 2200$) — the number stocks currently owned by Bob.

Each of the next $2n$ lines contains integers $a_i$ and $b_i$ ($0 \leq a_i, b_i \leq 10^9$), representing the stock price of stock $i$.

第一行包含一个整数 $n$（$1 \leq n \leq 2200$），表示 Bob 当前持有的股票种类数。

接下来的 $2n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$0 \leq a_i, b_i \leq 10^9$），表示第 $i$ 种股票的价格。

If it is impossible for Bob to achieve his goal, output a single integer $-1$.

Otherwise, output two integers $T$ and $E$, where $T$ is the minimum time in which he can achieve his goal, and $E$ is the minimum number of exchanges in which he can achieve his goal at time $T$.

如果鲍勃无法实现他的目标，则输出单个整数 $-1$。

否则，输出两个整数 $T$ 和 $E$，其中 $T$ 是他实现目标所需的最短时间，$E$ 是他在时间 $T$ 内实现目标所需的最少交换次数。

In the first example, Bob simply waits until time $t = 3$, when both stocks cost exactly the same amount.

In the second example, the optimum strategy is to exchange stock $2$ for stock $1$ at time $t = 1$, then exchange one share of stock $1$ for stock $3$ at time $t = 5$ (where both cost $15$) and then at time $t = 6$ exchange the second on for the stock number $4$ (when they cost $18$ and $17$, respectively). Note that he can achieve his goal also with only two exchanges, but this would take total time of $t = 9$, when he would finally be able to exchange the share number $2$ for the share number $3$.

In the third example, Bob can never achieve his goal, as the second stock is always strictly more expensive than the first one.

在第一个例子中，鲍勃只需等待至时刻 $t = 3$，此时两只股票的价格恰好完全相同。

在第二个例子中，最优策略是：在时刻 $t = 1$ 将股票 $2$ 兑换为股票 $1$；接着在时刻 $t = 5$（此时两者价格均为 $15$）将一股股票 $1$ 兑换为股票 $3$；最后在时刻 $t = 6$ 将第二股（即刚获得的那股股票 $3$）兑换为股票 $4$（此时它们的价格分别为 $18$ 和 $17$）。注意，他也可以仅通过两次兑换达成目标，但那样总共需耗时 $t = 9$，即直到该时刻他才最终能将股票 $2$ 兑换为股票 $3$。

在第三个例子中，鲍勃永远无法达成目标，因为股票 $2$ 的价格始终严格高于股票 $1$。