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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPA(i,s,e) for(int i=s; i<=e; i++)
#define REPD(i,s,e) for(int i=s; i>=e; i--)

typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int, int> PII;

int n, g;
const int MAX_N = 101;
const int MAX_M = 21;
int m[MAX_N], x[MAX_N][MAX_M], y[MAX_N][MAX_M], c[MAX_N][MAX_M];

const int MAX_V = 5000;		// 最大ノード番号
int v;						// 通算ノード番号
map<int,int> idx[2][MAX_N]; // 0は入ってくる側，1は出ていく側

struct edge {
	int to;		// 行き先
	int cap;	// 流量
	int cost;	// コスト
	int rev;	// 逆辺が格納されている番号
};

vector<edge> G[MAX_V], G2[MAX_V];
int dist[MAX_V];	// ノードまでの最小コスト
int prevv[MAX_V];	// 直前のノード
int preve[MAX_V];	// 直前のエッジ

const int INF = 1000000000;

void add_edge(int from, int to, int cap, int cost) {
	edge e;
	e.to = to, e.cap = cap, e.cost = cost, e.rev = G[to].size();
	G[from].push_back(e);
	e.to = from, e.cap = 0, e.cost = -cost, e.rev = G[from].size() - 1; // 準方向の辺はすでにaddしたので1を引く必要があるのに注意
	G[to].push_back(e);
}

// 最小費用流問題を解く
PII min_cost_flow(int s, int t, int f) {
	for(int i=0; i<v; i++) G2[i] = G[i];
	int res = 0;

	// 流量が限界になるまで流す
	int a = 0;	// ゴールについたクラス数
	int b = f;	// 最大まで流し切った時のために保存
	while(f > 0) {
		// ダイクストラ法で最短距離を検索
		priority_queue<PII, vector<PII>, greater<PII> > que;
		fill(dist, dist+v, INF);
		dist[s] = 0;
		que.push(PII(0, s));
		while(!que.empty()) {
			PII p = que.top();
			que.pop();
			int nv = p.second;
			if(dist[nv] < p.first) continue;

			for(int i=0; i<G2[nv].size(); i++) {
				edge& e = G2[nv][i];
				if(e.cap > 0 && dist[e.to] > dist[nv] + e.cost) {
					dist[e.to] = dist[nv] + e.cost;
					prevv[e.to] = nv;
					preve[e.to] = i;
					que.push(PII(dist[e.to], e.to));
				}
			}
		}

		if(dist[t] == INF) return PII(a, res);

		a++;
		int d = f;
		for(int nv=t; nv!=s; nv=prevv[nv]) {
			d = min(d, G2[prevv[nv]][preve[nv]].cap);
		}
		f -= d;
		res += d*dist[t];
		for(int nv=t; nv!=s; nv=prevv[nv]) {
			edge &e = G2[prevv[nv]][preve[nv]];
			e.cap = -d;
			G2[nv][e.rev].cap += d;
		}
	}

	return PII(b, res);
}

int main() {
	while(cin >> n, n) {
		// データのクリア
		REP(i,MAX_V) G[i].clear();
		REP(i,2) REP(j,MAX_N) idx[i][j].clear();

		// データの読み込み
		for(int i=1; i<n; i++) {
			cin >> m[i];
			REP(j, m[i]) cin >> x[i][j] >> y[i][j] >> c[i][j];
		}
		cin >> g;

		// グラフの作成を開始
		v = 0;
		idx[1][1][0] = v++; // 0番目の駅には0分の時点で着いている
		for(int q=1; q<n; q++) {
			// q番目の駅から出ていく列車の到着する先にとの間にエッジを張る
			for(map<int,int>::iterator it=idx[1][q].begin(); it!=idx[1][q].end(); ++it) {
				int time = it->first;		// q番目の駅に到着した時間
				for(int j=0; j<m[q]; j++) { // q番目の駅から出発する列車を調査
					if(x[q][j] >= time) {	// 到着した時点でまだ出発していない
						if(idx[0][q+1].count(y[q][j]) == 0) idx[0][q+1][y[q][j]] = v++;		// まだ登場していないノードならノードの番号を追加
						add_edge(it->second, idx[0][q+1][y[q][j]], 1, c[q][j]);
					}
				}
			}

			// 2つペアで管理されている駅上での発着をエッジで結ぶ
			for(map<int,int>::iterator it=idx[0][q+1].begin(); it!=idx[0][q+1].end(); ++it) {
				int time = it->first;
				if(idx[1][q+1].count(time) == 0) idx[1][q+1][time] = v++;					// まだ登場していないノードならノードの番号を追加
				add_edge(it->second, idx[1][q+1][time], 1, 0);								// 流量を制限するためのノードなのでコストは不要
			}
		}
		idx[0][n+1][0] = v++;

		// ゴールのノードへエッジを張る
		for(map<int,int>::iterator it=idx[1][n].begin(); it!=idx[1][n].end(); ++it) {
			add_edge(it->second, idx[0][n+1][0], 1, 0);
		}

		int sp = 0;
		int gp = v-1;
		PII res = min_cost_flow(sp, gp, g);
		if(res.first != 0) {
			cout << res.first << " " << res.second << endl;
		} else {
			cout << 0 << " " << 0 << endl;
		}
	}
}