题目描述 小玩一个游戏： 这个游戏有关，编号为,初始时， 只有第一关是解锁的。 对于第关，如果它解锁了，那么你可以：

花秒通过第关，然后你可以解锁第关 花秒通过第关，然后解锁第关。 只考虑通过每关游戏的时间，请问你最少要花多少秒，才能解锁第关。

输入格式 第一行一个整数. 接下来有行，每行三个整数，表示.

输出格式 一个整数，表示答案。

样例 输入样例1 5 100 200 3 50 10 1 100 200 5 150 1 2 输出样例1 350 输入样例2 10 1000 10 9 1000 10 10 1000 10 2 1000 10 3 1000 10 4 1000 10 5 1000 10 6 1000 10 7 1000 10 8 输出样例2 90 输入样例3 6 1000000000 1000000000 1 1000000000 1000000000 1 1000000000 1000000000 1 1000000000 1000000000 1 1000000000 1000000000 1

输出样例3 5000000000