School Excursion

Spring is the time for school trips. The University of Aizu Elementary School (Aizu University and Small) also had a plan for a school trip next year. It is a tradition to travel by train on school trips. This is because there are few opportunities to use the train in Aizuwakamatsu city.

However, the teachers were troubled by a complaint that arrived at the school. It said, "Because I was transferring at a certain station with a large number of people, it was a nuisance to other passengers using that station." Especially, after getting off the train, the passage from the platform was very crowded.

This is because the number of students in Aizu, large and small, has skyrocketed in recent years. The reason is that competitive programming has become very popular in Japan, and students have gathered at Aizu Daishō, which is training to train competitive programmers from elementary school.

As the director of the Aizu University and Small Competitive Programming Department, you are looking forward to your school trip. If you want to make your school trip a success, you have made suggestions to the teachers. "Act in each class and avoid arriving at the same station at the same time !! It's easy if you apply your knowledge of competitive programming !!"

When traveling so that multiple classes do not arrive at the same station at the same time (multiple classes can stay at the same station), find the maximum number of classes that can reach the destination from the departure station. Create a program that seeks the minimum fare for the time. However, if there are trains that arrive at a certain station and trains that depart at the same time, it is possible to make a connection. In other words, the time required for transit can be ignored.

Input

The input consists of multiple datasets. The number of datasets is 20 or less. The format of each data set is as follows.

n m1 x1,1 y1,1 c1,1 x1,2 y1,2 c1,2 ... x1, m1 y1, m1 c1, m1 m2 x2,1 y2,1 c2,1 x2,2 y2,2 c2,2 ... x2, m2 y2, m2 c2, m2 ... mn-1 xn-1,1 yn-1,1 cn-1,1 xn-1,2 yn-1,2 cn-1,2 ... xn-1, m2 yn-1, m2 cn-1, m2 g

n (2 ≤ n ≤ 100) represents the number of stations. The number of stations includes departure stations, destination stations, and transfer stations. The station that departs is counted as the first station, the station that transfers first is counted as the second station, and the destination is the nth station. mi represents the number of trains from the i-th station to the i + 1-th station. Information on mi (1 ≤ m ≤ 20) trains follows. xi, j yi, j ci, j represent the departure time (xi, j), arrival time (yi, j) and fare (ci, j) of the train from the i-th station to the i + 1th station. (0 ≤ xi, j, yi, j ≤ 200000 and xi, j ≤ yi, j) (1 ≤ ci, j ≤ 1000) followed by g (1 ≤ g ≤ 10). g represents the number of classes participating in the school trip. The numbers given (n, m, x, y, c, g) are all integers. The end of input is indicated by one line containing one 0.

Output

Output the number of classes that can arrive in one line and the minimum fare at that time in this order. If even one class cannot arrive, output 0 0.

Example

Input

2 4 1 2 10 2 2 5 1 3 20 2 3 10 10 3 2 1 2 5 0 3 4 3 10 11 100 2 12 2 12 12 3 10 0

Output

2 15 2 111

inputFormat

Input

The input consists of multiple datasets. The number of datasets is 20 or less. The format of each data set is as follows.

n m1 x1,1 y1,1 c1,1 x1,2 y1,2 c1,2 ... x1, m1 y1, m1 c1, m1 m2 x2,1 y2,1 c2,1 x2,2 y2,2 c2,2 ... x2, m2 y2, m2 c2, m2 ... mn-1 xn-1,1 yn-1,1 cn-1,1 xn-1,2 yn-1,2 cn-1,2 ... xn-1, m2 yn-1, m2 cn-1, m2 g

n (2 ≤ n ≤ 100) represents the number of stations. The number of stations includes departure stations, destination stations, and transfer stations. The station that departs is counted as the first station, the station that transfers first is counted as the second station, and the destination is the nth station. mi represents the number of trains from the i-th station to the i + 1-th station. Information on mi (1 ≤ m ≤ 20) trains follows. xi, j yi, j ci, j represent the departure time (xi, j), arrival time (yi, j) and fare (ci, j) of the train from the i-th station to the i + 1th station. (0 ≤ xi, j, yi, j ≤ 200000 and xi, j ≤ yi, j) (1 ≤ ci, j ≤ 1000) followed by g (1 ≤ g ≤ 10). g represents the number of classes participating in the school trip. The numbers given (n, m, x, y, c, g) are all integers. The end of input is indicated by one line containing one 0.

outputFormat

Output

Output the number of classes that can arrive in one line and the minimum fare at that time in this order. If even one class cannot arrive, output 0 0.

Example

Input

2 4 1 2 10 2 2 5 1 3 20 2 3 10 10 3 2 1 2 5 0 3 4 3 10 11 100 2 12 2 12 12 3 10 0

Output

2 15 2 111

样例

2
4
1 2 10
2 2 5
1 3 20
2 3 10
10
3
2
1 2 5
0 3 4
3
10 11 100
2 12 2
12 12 3
10
0

2 15
2 111

</p>