题目描述

有n个巴士站，编号1..n，中央站为1。有2n条巴士线路；第i条线路的起点为⌈i/2⌉，终点e_i。每条线路每天有且只有一班车，于每日l_i时刻出发，行驶d_i小时到达终点。每天24小时。

Aoki于第一天0时到达中央1号站，必须乘每条巴士线路恰好一次，最后回到中央1号站。线路即使起终点相同也按输入行区分，乘过某条线路后不得再次乘它。允许在车站等待下一班；若到达时刻恰等于发车时刻，可以立即换乘。所有线路在每天都按同一时刻运行，路线中任何一条线路可等到未来某天乘坐。

保证存在满足每条线路恰一次、1号站首尾的行程。求从第1天0时到最终返回的最短总小时数。

输入

第一行n。接下来2n行，第i行e_i,l_i,d_i。

输出

最短总小时数，一个整数。

本地完整范围

2≤n≤1000，1≤e_i≤n且e_i≠⌈i/2⌉；0≤l_i<24，1≤d_i≤1000。每站恰有两条出线、两条入线，所有站在底层无向图中连通，所以有从1出发的有向Euler回路。相同起终点的不同线路允许并存。

输入样例 1

2
2 1 5
2 0 3
1 4 4
1 6 3

输出样例 1

32

输入样例 2

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

输出样例 2

192

本地修订说明

原页范围“l≤e_i≤n,0≤l_i≤1000,e_i≠i”有明显字段错排，并缺d_i完整范围。本版本按每日24小时模型规范发车时刻为0..23、耗时1..1000，禁止终点等于实际起站而非边编号；Euler可行性保证等价展开为每站两入两出及连通。两套原样例保留，不冒称本地完整范围为官方原卷。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：原范围字段错排、d缺失；本地规范l每日0..23，d1..1000，e≠实际起站，双出双入且连通，保留每条线恰一次的核心目标、两套样例与最短绝对时间输出。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1739。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。