Jim Ratt 刚刚加入了一家当地的健身中心。他非常兴奋，因为他要进行一套包含 10 台器械的循环训练，总共循环 3 次。他在每台器械上都有固定的使用时间，以及使用后的固定恢复时间。Jim 虽然不是世界上最聪明的人，但在没有其他干扰的情况下，他也能轻松算出自己完成训练需要多长时间。

当然，Jim 并不是健身中心里唯一的人。当 Jim 到达时，总会有另外 10 个人在那里，每个人都在独占使用这 10 台器械中的一台。和 Jim 一样，每个人在器械上的使用时间和恢复时间也是固定的。这有时会导致 Jim 必须等待某台器械，而 Jim 的使用也会导致其他人不得不等待（不过，如果 Jim 和另一个人同时想要开始使用某台器械，Jim 会礼貌地让对方先用）。Jim 去健身中心的次数足够多，以至于他很清楚每个人的使用时间和恢复时间，但他很难确定自己完成训练需要多长时间。这就是你需要发挥编程能力的地方。

输入格式

输入的第一行包含 20 个整数；前两个整数给出 Jim 在器械 1 上的使用时间和恢复时间，接下来的两个整数给出 Jim 在器械 2 上的使用时间和恢复时间，以此类推。接下来的 1 行包含 3 个整数 $u, r, t$；前两个值是正在使用器械 1 的人的使用时间和恢复时间，$t$ 是他/她第一次开始使用该器械的时间。接下来的 9 行以类似的方式指定了器械 2 到 10 的信息。所有使用时间和恢复时间均为正整数且 $\le 5\,000\,000$，所有开始时间 $t$ 满足 $|t| \le 5\,000\,000$。你应该假设 Jim 在时间 0 时准备好使用器械 1。

输出格式

显示 Jim 完成训练的时间，即他第三次完成器械 10 的使用时间的那一刻（不要计算该器械最后一次的恢复时间）。

样例

输入 1

5 5 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 1
8 3 0
1 1 0
1 1 0
1 1 0
1 1 0
1 1 0
1 1 0
1 1 0
1 1 0

输出 1

100