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

题目描述

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

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

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

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

输入格式

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

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

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

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

输出格式

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

样例

输入样例

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

输出样例

8