Problem Description

Patrik and Josip are riding a tram. They ride for a total of $n$ stops.

At every stop after the boarding stop, exactly one of the following events happens upon arrival:

• Patrik says: $t$ minutes have passed since we boarded.

• Josip says: It took $t$ minutes to get here from stop $y$.

Now, based on this information, find which two stops have the shortest travel time between them, and output that time.

Input Format

The input has $n$ lines.

The first line contains an integer $n$ ($2\le n\le1000$), the number of stops.

The next $n-1$ lines describe the event that happened at stop $i+1$ on line $i$:

• Type 1: $\texttt{Patrik } t_i$ ($1\le t_i\le10^9$).

• Type 2: $\texttt{Josip } y_i\texttt{ }t_i$ ($y_i < i + 1$, $1\le t_i\le10^9$).

Each stop is at a different position.

Output Format

Output one line with three integers $t$, $x_1$, $x_2$, representing the shortest time, and the start and end stops that achieve this shortest time.

If there are multiple answers, output the lexicographically smallest one.

4
Patrik 3
Patrik 5
Josip 1 7

2 2 3

2
Josip 1 5

5 1 2

5
Patrik 4
Josip 2 4
Josip 2 6
Josip 4 2

2 3 4

Hint

This problem uses bundled testdata.

The full score for this problem is $50$ points.

Translated by ChatGPT 5