Official Approval#2996

Statement Discussion

Official Approval

1 second

64 megabytes

Very easy

In the department that issues official documents, there are $N$ employees (including the director), such that:

Each employee (except the director) has one superior.
Each employee has between $0$ and $4$ subordinate employees.
The superior of my superior is not my direct superior.
The subordinate of my subordinate is not my direct subordinate.

To receive the final approved document, you need to collect a sequence of approvals, starting from one of the subordinates (if any), then the concerned employee or director. Each approval requires paying an official processing fee to that employee.

What is the minimum total official fee required to obtain the final document from the director?

Input

The first line contains $N$ , the number of employees in the department. Then follow $N$ lines. In the $i$ -th line (i = 1, \ldots, N), the data for the $i$ -th employee is given as: D_i — the official processing fee, K_i — the number of subordinates, and their numbers. The director has number $1$ . All numbers are natural numbers not exceeding $100$ .

Output

Output the answer to the problem.

Examples

Example 1

Loading

Loading

i = 1, \dots, N

D_{i}

K_{i}