In Card Captor Sakura, Sakura is a lovely girl. One day, she opens a magic box containing many cards. Every card has a respective natural force in the real world, such as wind, water, YY, LMY, and so on. Suddenly a gust of wind blows away these cards. Sakura only has a card called “THE_WINDY” in her hand. Sakura knows if any card is not found, disaster comes. So she must collect all the cards. Cards can only be collected one by one. Suppose there are N cards to be collected. It takes Ti to collect the ith card, 1≤i≤N. For the ith card, there is a corresponding card Pi. If card Pi has been collected, it only takes time ti to collect the ith card, where ti<Ti.
Your task is to help Sakura design a schedule that takes the shortest time to collect all cards.
The input consists of several test cases. Each test case starts with a line giving the number N of cards (1≤N≤100). Each of the next N lines describes a card.
Every card has the format: Name1 Ti Name2 ti, where Name1 and Name2 are cards’ names, consisting of uppercase letters and underlines. The length of cards’ names is no more than 20 characters. Card Name1 is a card to be collected. It takes Ti to collect Card Name1 without Card Name2. And it takes ti to collect Card Name1 with Card Name2, where ti<Ti.
End of input is indicated by a line consisting of a single 0.
For each test case, output a single line. Each line should give a single integer: the shortest time.
5 THE_FLY 67 THE_WINDY 39 THE_SHADOW 97 THE_WINDY 49 THE_WATER 139 THE_FLY 69 THE_RAIN 37 THE_WATER 18 THE_WOOD 5 THE_RAIN 1 1 THE_LOOP 35 THE_LOOP 25 0
176 35
Migrated from old NTUJ.
2009 Shanghai Network Contest
| No. | Testdata Range | Score |
|---|