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
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define NUM 10000

enum Type{
	COME,
	GO,
	SQUEEZE,
};

struct Node{
	int time_value;
};

//辺を表す構造体{行先、容量、コスト、逆辺のインデックス}
struct Edge{
	Edge(int arg_to,int arg_capacity,int arg_cost,int arg_rev_index){
		to = arg_to;
		capacity = arg_capacity;
		cost = arg_cost;
		rev_index = arg_rev_index;
	}

	int to,capacity,cost,rev_index;
};

int num_station;
Node nodes[NUM];
vector<int> ST_INFO[101][3];

int V; //頂点数
vector<Edge> G[NUM]; //グラフの隣接リスト表現
int dist[NUM]; //最短距離
int pre_node[NUM],pre_edge[NUM]; //直前の頂点と辺


//fromからtoへ向かう容量capacity,コストcostの辺をグラフに追加する
void add_edge(int from,int to,int capacity,int cost){
	G[from].push_back(Edge(to,capacity,cost,G[to].size()));
	G[to].push_back(Edge(from,0,-cost,G[from].size()-1));
}

//sourceからsinkへの、流量flowの最小費用流を求める
//流せない場合は-1を返す
int min_cost_flow(int source,int sink,int flow){
	int ret = 0;
	while(flow > 0){
		//ベルマンフォード方により、source-sink間最短経路を求める
		for(int i = 0; i < V; i++)dist[i] = BIG_NUM;
		dist[source] = 0;
		bool update = true;
		while(update){
			update = false;
			for(int node_id = 0; node_id < V; node_id++){
				if(dist[node_id] == BIG_NUM)continue;
				for(int i = 0; i < G[node_id].size(); i++){
					Edge &e = G[node_id][i];
					if(e.capacity > 0 && dist[e.to] > dist[node_id]+e.cost){
						dist[e.to] = dist[node_id]+e.cost; //node_idを経由した方が早い場合
						pre_node[e.to] = node_id;
						pre_edge[e.to] = i;
						update = true;
					}
				}
			}
		}

		if(dist[sink] == BIG_NUM){
			//これ以上流せない
			return -1;
		}

		//source-sink間最短路に沿って目いっぱい流す
		int tmp_flow = flow;
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			tmp_flow = min(tmp_flow,G[pre_node[node_id]][pre_edge[node_id]].capacity);
		}
		flow -= tmp_flow;
		ret += tmp_flow*dist[sink];
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			Edge &e = G[pre_node[node_id]][pre_edge[node_id]];
			e.capacity -= tmp_flow;
			G[node_id][e.rev_index].capacity += tmp_flow;
		}
	}
	return ret;
}

void func(){

	for(int i = 0; i < NUM; i++)G[i].clear();

	for(int i = 0; i < num_station; i++){
		ST_INFO[i][COME].clear();
		ST_INFO[i][GO].clear();
		ST_INFO[i][SQUEEZE].clear();
	}

	int source = 0,sink = 1,index = 2;
	int num_train,start_time,arrive_time,cost;

	bool FLG;
	int from,to;

	//駅0の情報を取得
	scanf("%d",&num_train);

	for(int loop = 0; loop < num_train; loop++){
		scanf("%d %d %d",&start_time,&arrive_time,&cost);


		//既に出現した出発時刻ではないか調べる
		FLG = false;
		for(int i = 0; i < ST_INFO[0][GO].size(); i++){
			if(nodes[ST_INFO[0][GO][i]].time_value == start_time){
				FLG = true;
				from = ST_INFO[0][GO][i];
			}
		}
		if(!FLG){
			ST_INFO[0][GO].push_back(index);
			nodes[index].time_value = start_time;
			from = index;
			index++;
		}

		//既に出現した到着時刻ではないか調べる
		FLG = false;
		for(int i = 0; i < ST_INFO[1][COME].size(); i++){
			if(nodes[ST_INFO[1][COME][i]].time_value == arrive_time){
				FLG = true;
				to = ST_INFO[1][COME][i];
			}
		}
		if(!FLG){
			ST_INFO[1][COME].push_back(index);
			nodes[index].time_value = arrive_time;
			to = index;
			index++;
		}

		add_edge(from,to,1,cost); //辺を張る
	}

	for(int station = 1; station <= num_station-2; station++){

		//到着時刻ノードに、一対一対応で、流量を絞るためのノードへ辺を張る
		for(int i = 0; i < ST_INFO[station][COME].size(); i++){
			nodes[index].time_value = nodes[ST_INFO[station][COME][i]].time_value;
			ST_INFO[station][SQUEEZE].push_back(index);
			add_edge(ST_INFO[station][COME][i],index,1,0);
			index++;
		}

		scanf("%d",&num_train);

		for(int loop = 0; loop < num_train; loop++){
			scanf("%d %d %d",&start_time,&arrive_time,&cost);

			//既に出現した出発時刻ではないか調べる
			FLG = false;
			for(int i = 0; i < ST_INFO[station][GO].size(); i++){
				if(nodes[ST_INFO[station][GO][i]].time_value == start_time){
					FLG = true;
					from = ST_INFO[station][GO][i];
				}
			}
			if(!FLG){
				ST_INFO[station][GO].push_back(index);
				nodes[index].time_value = start_time;
				from = index;
				index++;
			}

			//既に出現した到着時刻ではないか調べる
			FLG = false;
			for(int i = 0; i < ST_INFO[station+1][COME].size(); i++){
				if(nodes[ST_INFO[station+1][COME][i]].time_value == arrive_time){
					FLG = true;
					to = ST_INFO[station+1][COME][i];
				}
			}
			if(!FLG){
				ST_INFO[station+1][COME].push_back(index);
				nodes[index].time_value = arrive_time;
				to = index;
				index++;
			}

			add_edge(from,to,1,cost); //辺を張る

			//★★squeezeノードから、出発ノードに辺を張る
			for(int i = 0; i < ST_INFO[station][SQUEEZE].size(); i++){
				if(nodes[ST_INFO[station][SQUEEZE][i]].time_value <= start_time){ //出発時刻前に到着しているなら張る
					add_edge(ST_INFO[station][SQUEEZE][i],from,1,0);
				}
			}
		}
	}

	//駅n-1の到着ノードから、sinkへ容量1の辺を張る
	for(int i = 0; i < ST_INFO[num_station-1][COME].size(); i++){
		add_edge(ST_INFO[num_station-1][COME][i],sink,1,0);
	}

	int num_class;
	scanf("%d",&num_class);

	int class_index[num_class];
	for(int i = 0; i < num_class; i++)class_index[i] = index++;

	//sourceから各クラスに容量1の辺を張る
	for(int i = 0; i < num_class; i++){
		add_edge(source,class_index[i],1,0);
	}

	//各クラスから、駅1の出発時刻に辺を張る
	for(int i = 0; i < num_class; i++){
		for(int k = 0; k < ST_INFO[0][GO].size(); k++){
			add_edge(class_index[i],ST_INFO[0][GO][k],1,0);
		}
	}

	V = index;

	int flow = 0,min_cost = 0,ret;

	for(int i = 0; i < num_class; i++){
		ret = min_cost_flow(source,sink,1);
		if(ret == -1)break;
		flow++;
		min_cost += ret;
	}

	printf("%d %d\n",flow,min_cost);
}

int main(){

	while(true){
		scanf("%d",&num_station);
		if(num_station == 0)break;

		func();
	}

	return 0;
}

