#2848. 不要牺牲

不要牺牲

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你是 MIB\red{MIB(}theMoneyIsBeautiful\red{the Money Is Beautiful)}的一个机密负责人.今天你并不轻松,因为你被 分配了一个艰巨的任务:在"theRock\red{the Rock}"偷一些珠宝。你对"theRock\red{the Rock}"了解多少呢?这是 一个在岛上的监狱,而且据说由于它陡峭的悬崖和特殊的设计,没有人能逃出它。但是,现 在已经没有犯人住在那里了,它变成了一个博物馆。你知道唯一潜入它的路就是地下火葬场 (现在用来烧掉日常垃圾)。

大量的管道连接着这些火葬场。你被告知了这些火葬场和管道, 试着在得到珠宝后,ASAP\red{ASAP(}翻译的人加注:大家以后可以用的缩写,assoonaspossible\red{as soon as possible)} 地离开整个博物馆。希望你不要被烧到。

每个火葬场被描述成两个整数 b\red{b }c\red{c}。一开始,所有的火葬厂都是进入清理状态。这个 状态要持续 c\red{c }秒钟。然后持续 b\red{b }秒种的放火状态。这两个状态交替进行。当一个火葬场将要 放火时,你不能经过它(翻译的人加注:比如 t1\red{t1 }t2\red{t2 }是清理,t2\red{t2 }t3\red{t3 }是放火,则在 t2\red{t2} 这个时间点你不能经过)。

但是当它将要进入清理状态时,却是安全的。你在管子里走的时 间也被计算在整个时间中(翻译的人加注:也就是说你可以蹲在管道里"浪费"时间)。告 诉我什么时候来接你。

输入格式

每个测试点的第一行是一个整数 n\red{n}。它表示这里有 n+1\red{n + 1 }个火葬厂。最初的位置是在 0\red{0} 号火葬场,目的地是 n\red{n }号火葬厂。

然后跟着 n\red{n }个行,每行两个整数 b(i)\red{b(i)}c(i)\red{c(i),}描述了(i1)\red{(i -1)}号火葬场的两个状态的时间长度(b\red{b }是放火时间,c\red{c }是清理时间,注意 n\red{n }号火葬场是你 的出口,所以没有什么信息)。

N\red{N }行之后,是一个整数 m\red{m }表示管道的条数。

随后的 m\red{m }行每行 3\red{3}个整数 x,y,t\red{x,y,t,}表示了 x\red{x }号和 y\red{y }号之间管道的最少行走时间是 t\red{t}。你可以假设 0<=n<=777\red{0 <= n <= 777,} 1<=m<=33333\red{1 <= m <= 33333 }而且结果不会超过 INTMAX\red{INT_MAX}

输出格式

对于每个测试点,输出一个最早时间好让我来接你。

样例

输入样例

2
3 2
3 3
2
0 1 4
1 2 2

输出样例

8

国庆集训9

未参加
状态
已结束
规则
IOI
题目
4
开始于
2022-10-4 13:45
结束于
2022-10-4 17:15
持续时间
3.5 小时
主持人
参赛人数
13