DWITE Contest

Test Case for Question #3 in DWITE 2007-2008 High School Round 3

Contest: DWITE 2007-2008 High School Round 3
Question: #3
Input File: DATA3.txt
Output File: OUT3.txt


Input

25
5
one_1 1 5
one_2 2 5
one_3 3 5
one_4 4 5
one_5 5 5
25
10
two_1 3 5
two_2 4 5
two_3 3 5
two_4 2 5
two_5 1 5
two_6 4 5
two_7 3 5
two_8 2 5
two_9 1 5
two_10 4 5
25
5
three_1 5 10
three_2 5 10
three_3 4 8
three_4 4 8
three_5 4 8
1
5
four_1 5 2
four_2 4 3
four_3 3 4
four_4 4 5
four_5 5 6
20
4
five_1 5 10
five_2 5 10
five_3 4 8
five_4 3 2




Output

15
18
12
0
12