Processing math: 100%
编程题
                ### 问题描述

《明日方舟》是一款魔物主题的策略手游。这一天,鹰角出了一个只有一条数轴的地图,数轴可以看做无限长,数轴的最右边是博士,你需要保护博士。一开始地图上会生成 n 只海嗣,第 i 只海嗣的起点是 s[i],每秒移动速度是 t[i],所有的海嗣每秒都会向右移动。

现在你是寒芒克洛斯,每秒开始时你可以击杀一只海嗣,你从 0 时刻开始对海嗣进行攻击,同时你希望所有的海嗣都会离博士越远越好,现在请问寒芒克洛斯可以使得海嗣移动的最远位置最小值是多少?

注:在每个时刻开始时,寒芒克洛斯会先攻击海嗣,攻击时间可以忽略不计,在锁定的海嗣被击杀后,海嗣才会开始移动,例如只有 2 只海嗣,寒芒克洛斯会在 0 时刻击杀一只,剩下的一只移动了 1 秒后到达了 1 时刻,寒芒克洛斯再将其击杀。

不会存在海嗣碰到博士导致游戏提前结束的情况。

输入格式

第一行输入一个整数 n ,表示海嗣的数量。

接下来 n 行输入,每行 2 个整数,表示海嗣的起点和每秒移动速度。

输出格式

输出一个整数,表示海嗣移动的最远位置的最小值。

样例输入

4
1 6
12 3
16 10
23 2

样例输出

25

说明

0 时刻攻击第 3 只海嗣:16+10×0=16

1 时刻攻击第 4 只海嗣:23+2×1=25

2 时刻攻击第 1 只海嗣:1+6×2=13

3 时刻攻击第 2 只海嗣:12+3×3=21

移动最远的海嗣距离为 25,同时也是所有攻击方法中海嗣移动最远距离的最小值。

评测数据规模

1n105,1s[i],t[i]109

查看答案
赣ICP备20007335号-2