警告:此问题有不寻常的内存限制!
Bob 决定,他不会浪费自己的黄金岁月为一家大公司实施 GUI 表单,而是在雷克雅未克证券交易所谋生。雷克雅未克证券交易所是世界上唯一的实际证券交易所。唯一的交易类型是用一股股票 $$$x$$$ 并将其交换为一股股票 $$$y$$$,前提是股票 $$$x$$$ 的当前价格至少是股票 $$$y$$$ 的当前价格。
SER 上列出了 Bob 感兴趣的 $$$2n$$$ 股票,编号从 $$$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$$$时刻能够实现目标的最少交换次数。
示例
输入 #1
1 3 10 1 16
输出 #1
3 1
输入 #2
2 3 0 2 1 1 10 1 11
输出 #2
6 3
输入 #3
1 42 42 47 47
输出 #3
-1
输入#4
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
输出#4
434847 11
输入 #5
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
输出 #5
1010327 11
注意
在第一个示例中,Bob 只是等待时间 $$$t = 3$$$,此时两只股票的价格完全相同。
在第二个示例中,最佳策略是在 $$$t = 1$$$ 时将股票 $$$2$$$ 换成股票 $$$1$$$,然后在 $$$t = 5$$$ 时将一股股票 $$$1$$$ 换成股票 $$$3$$$(两者成本为 $$$15$$$),然后在 $$$t = 6$$$ 时将第二股股票交换库存编号为 $$$4$$$(当它们的价格分别为 $$$18$$$ 和 $$$17$$$ 时)。请注意,他也可以仅通过两次交换来实现他的目标,但这将花费 $$$t = 9$$$ 的总时间,此时他最终能够将股份编号 $$$2$$$ 交换为股份编号 $$$3$$$。
在第三个例子中,鲍勃永远无法实现他的目标,因为第二只股票总是比第一只股票更贵。