← 返回题目列表

Codeforces · 1178/H

H. 证券交易所

中文机器翻译题面 查看原题

警告:此问题有不寻常的内存限制!

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$$$。

在第三个例子中,鲍勃永远无法实现他的目标,因为第二只股票总是比第一只股票更贵。