CF1178H Stock Exchange

警告：本题的内存限制不同寻常！ Bob 决定不再浪费自己的黄金岁月为大型公司开发 GUI 表单，而是要在雷克雅未克证券交易所（Stock Exchange Reykjavik）上谋生。雷克雅未克证券交易所是世界上唯一真正的证券交易所。唯一允许的交易方式是：用一股股票 $x$ 换取一股股票 $y$，前提是当前股票 $x$ 的价格不少于股票 $y$ 的价格。 在 SER 上有 $2n$ 支股票是 Bob 感兴趣的，编号从 $1$ 到 $2n$。Bob 目前拥有股票 $1$ 到 $n$ 各一股，他希望将来能拥有股票 $n+1$ 到 $2n$ 各一股。 Bob 已经预测出了每支股票的价格——在时间 $t \geq 0$ 时，第 $i$ 支股票的价格为 $a_i \cdot \lfloor t \rfloor + b_i$。当前时间为 $t = 0$。请你帮助 Bob 找出他最早能拥有每支股票 $n+1$ 到 $2n$ 各一股的时刻，以及在该时刻所需进行的最少股票交换次数。 你可以假设证券交易所任何时刻都有无限量的每种股票可供交换。

第一行包含一个整数 $n$（$1 \leq n \leq 2200$），表示 Bob 当前拥有的股票数量。 接下来的 $2n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$0 \leq a_i, b_i \leq 10^9$），表示第 $i$ 支股票的价格。

如果 Bob 无法实现目标，输出一个整数 $-1$。 否则，输出两个整数 $T$ 和 $E$，其中 $T$ 表示他能实现目标的最早时刻，$E$ 表示在时刻 $T$ 所需进行的最少交换次数。

在第一个样例中，Bob 只需等待到 $t = 3$，此时两支股票价格正好相等。 在第二个样例中，最优策略是在 $t = 1$ 时用股票 $2$ 换股票 $1$，然后在 $t = 5$ 时用一股股票 $1$ 换股票 $3$（此时两者价格均为 $15$），接着在 $t = 6$ 时用另一股股票 $1$ 换股票 $4$（此时价格分别为 $18$ 和 $17$）。注意，他也可以只用两次交换完成目标，但那样需要等到 $t = 9$，此时他才能用股票 $2$ 换股票 $3$。 在第三个样例中，Bob 永远无法实现目标，因为第二支股票的价格始终严格高于第一支股票。 由 ChatGPT 4.1 翻译