Rock Man

Interview

Time limit8sMemory limit512 MB

Summary

Each tool takes day1 days normally or day2 if its support tool is finished first; order the tools to minimize total days.

Level: Medium6 of 10
Topics: Graph, Greedy, Implementation, Sorting
Solved: No attempts yet

Problem

You were a well known craftsman in the stone age, and you spent your life carving tools out of natural stone. Your works are still displayed with respect in museums in 2006. Most visitors, though, do not linger in front of them. Watching that from Heaven, you remembered the days you had worked yourself to the bone.

On one of your busiest days you received a number of orders for tools. Each order asked for a different tool. Filling a single order from bare stone often took several days. But a tool you had already finished let you carve a new tool faster. For every tool in the order list there is exactly one tool that can support carving it.

Carving one tool takes one of two amounts of time. With no support tool it takes $day_1$ days. If the support tool is already finished when you start, it takes only $day_2$ days. Some tools list themselves as their own support tool, and such a tool cannot support itself.

You carve one tool at a time, so the whole schedule lasts the sum of the per tool day counts. Find the smallest number of days needed to fill every order.

Input

The input is a series of test cases. Each case begins with a line holding a single integer $N$ , the number of ordered tools.

Then $N$ lines follow. Each line specifies one order with four values separated by one or more spaces, in the order $name$ , $day_1$ , $sup$ , $day_2$ . $name$ is the name of the tool in that order, $day_1$ is the number of days needed to make the tool without any support tool, $sup$ is the name of the tool that can support carving it, and $day_2$ is the number of days needed to make the tool after $sup$ is finished.

The input ends with the case where $N = 0$ . Do not process that case.

$N \le 1000$
$name$ has at most 32 non-space characters and is unique within a test case
$sup$ is one of the names given in the same test case, and it may be $name$ itself
$0 < day_2 < day_1 < 20000$

Output

For each test case, print one line holding the minimum number of days required to fill all $N$ orders.

Examples3

Example 1

Input

3
gu 20 pa 10
ci 20 gu 10
pa 20 ci 10
2
tool 20 tool 10
product 1000 tool 10
8
fishhook 21 disk 3
mill 14 axe 7
boomerang 56 sundial 28
flint 35 fishhook 5
axe 35 flint 14
disk 42 disk 2
sundial 14 disk 7
hammer 28 mill 7
0

Expected output

40
30
113

Example 2
Input
```
1
chisel 19999 chisel 1
0
```
Expected output
```
19999
```

Example 3

Input

2
spear 100 knife 1
knife 100 spear 99
0

Expected output