13839번 - Rock Man 다국어

You were the master craftsman in the stone age, and you devoted your life to carving many varieties of tools out of natural stones. Your works have ever been displayed respectfully in many museums, even in 2006 A.D. However, most people visiting the museums do not spend so much time to look at your works. Seeing the situation from the Heaven, you brought back memories of those days you had frantically lived.

One day in your busiest days, you got a number of orders for making tools. Each order requested one tool which was different from the other orders. It often took some days to fill one order without special tools. But you could use tools which you had already made completely, in order to carve new tools more quickly. For each tool in the list of the orders, there was exactly one tool which could support carving it.

In those days, your schedule to fill the orders was not so efficient. You are now thinking of making the most efficient schedule, i.e. the schedule for all orders being filled in the shortest days, using the program you are going to write.

The input consists of a series of test cases. Each case begins with a line containing a single integer N which represents the number of ordered tools.

Then N lines follow, each specifying an order by four elements separated by one or more space: name, day₁ , sup and day₂ . name is the name of the tool in the corresponding order. day₁ is the number of required days to make the tool without any support tool. sup is the name of the tool that can support carving the target tool. day₂ is the number of required days make the tool with the corresponding support tool.

The input terminates with the case where N = 0. You should not process this case.

You can assume that the input follows the constraints below:

• N ≤ 1000;
• name consists of no longer than 32 non-space characters, and is unique in each case;
• sup is one of all names given in the same case; and
• 0 < day2 < day1 < 20000.

For each test case, output a single line containing an integer which represents the minimum number of days required to fill all N orders.