[Technical] The Courier Problem

Background

A courier encountered some small problems. The daily delivery process is both tedious and time-consuming. The reason is that the delivery destinations require different delivery times.

Problem Description

Given an undirected graph where each node has opening and closing times. Starting from the starting point, visit all nodes when they are open. Find the latest possible departure time when the total time spent is minimized. Each day has a total of 1440 time units. When reaching the closing time, the node is already closed. For example, if a node closes at time 100, arriving at time 100 is not considered a successful visit. Node 1 is fixed as the starting point, and node 1 has no opening/closing times.

Input Format

Total n+m lines.

Line 1 contains $n$ and $m$, representing the number of nodes and edges.

Lines 2 to n each contain two integers $t^o_n$ and $t^c_n$ representing the opening time and closing time of this node, where n is the line number.

Lines n+1 to n+m each contain $a$ $b$ $t_{ab}$, representing the starting point, ending point, and time required to traverse the edge.

Output Format

Output only one integer representing the departure time. If impossible to complete, output -1.

Input/Output Example

Input

2 1
0 1440
1 2 1

Output

1438

Explanation

For all data, $1<n\leqslant10000$, $0<m\leqslant10000$. (I made up the data range)

However, my knowledge is limited and I cannot solve this problem. Maybe after some time I’ll find it’s actually a very simple problem.

If the data is guaranteed to have a solution, there might be some clever tricks, but if a solution isn’t guaranteed, then I can only think of brute force.

Also, this problem can be modified, such as finding the earliest finish time. This way running brute force might be a bit better.