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 <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define REP(i, n)				for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)			for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF						(int)2e9
#define MOD						(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)				(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)				(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)			((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)				(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)				(!IsOdd((x)))						
#define ArrayLength(x)			(sizeof( x ) / sizeof( x[ 0 ]))
#define	MAX_QWORD				((QWORD)0xFFFFFFFFFFFFFFFF)
#define M_PI					3.14159265358979323846
typedef long long				ll;
typedef unsigned long long int	QWORD;
typedef pair<ll, ll>			P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
// 枝定義
struct Edge
{
	int	toIdx;
	int	revIdx;
	int	cost;
	int	cap;
	Edge(){}
	Edge(int to, int rev, int costArg, int capArg): toIdx(to), revIdx(rev), cost(costArg), cap(capArg){}
};
 
// 最小費用流
class MinCostFlow 
{
private:
	vector<vector<Edge>> G;
	vector<int> dist;
	vector<int> prevV;
	vector<int> prevE;
	int nodeMax;

	// 各節の最短経路を算出
	void BellmanFord(int startPos, int endPos, int flow) 
	{
		fill(dist.begin(), dist.end(), INF);
		dist[startPos] = 0;

		bool update = true;
		while (update) {
			update = false;
			for (int v = 0; v < nodeMax; v++) {
				if (dist[v] == INF) continue;
				for (int i = 0; i < (int)G[v].size(); i++) {
					Edge &edge = G[v][i];
					if (0 < edge.cap) {
						int to = edge.toIdx;
						int nextDist = dist[v] + edge.cost;
						if (dist[to] > nextDist) {
							dist[to] = nextDist;
							prevV[to] = v;
							prevE[to] = i;
							update = true;
						}
					}
				}
			}
		}
	}

public:
	int totalCostRes;
	int totalFlowRes;

public:
	MinCostFlow(int N)
	{
		G.resize(N);
		dist.resize(N);
		prevV.resize(N);
		prevE.resize(N);
	}

	// 枝を追加
	void AddEdge(int from, int to, int cap, int cost)
	{
		int revIdxTo = G[to].size();
		int revIdxFrom = G[from].size();
		G[from].emplace_back(to, revIdxTo, cost, cap);
		G[to].emplace_back(from, revIdxFrom, -cost, 0);
	}

	// 最小費用流を求める
	int GetMinCostFlow(int startPos, int endPos, int totalFlowReq)
	{
		int remainFlow;
		
		totalFlowRes = 0;
		totalCostRes = 0;
		remainFlow = totalFlowReq;
		nodeMax = (int)G.size();
		while (0 < remainFlow) {
			BellmanFord(startPos, endPos, remainFlow);
			if (dist[endPos] == INF) {
				return -1;
			}

			// 流せる最大量
			int flowOne = remainFlow;
			for (int v = endPos; v != startPos; v = prevV[v]) {
				flowOne = min(flowOne, G[prevV[v]][prevE[v]].cap);
			}
			remainFlow -= flowOne;
			totalFlowRes += flowOne;
			totalCostRes += flowOne * dist[endPos];

			// 枝の状態を更新
			for (int v = endPos; v != startPos; v = prevV[v]) {
				Edge &edge = G[prevV[v]][prevE[v]];
				edge.cap -= flowOne;
				G[v][edge.revIdx].cap += flowOne;
			}
		}

		return totalCostRes;
	}
};

// ベクターを値とインデックスのマップに圧縮
template <class T> 
map<T, int> compressVectorToMap(vector<T> vect)
{
	int cmpIdx = 0;
	map<T, int> idxTblMap;
	
	// 重複削除
	sort(vect.begin(), vect.end());
	vect.erase(unique(vect.begin(), vect.end()), vect.end());
	
	// 昇順にインデックスを割り当て
	for (auto one : vect) {
		idxTblMap[one] = cmpIdx;
		cmpIdx++;
	}

	return idxTblMap;
}

struct trainInfo
{
	int startTime;
	int stopTime;
	int cost;
};

void execOne(int ekiNum)
{
	int totalTrainNum = 0;
	int kukanNum = ekiNum - 1;
	vector<int> timeCmp;
	vector<vector<trainInfo>> stTrainInfo(kukanNum);
	vector<vector<int>> ekiTimeList(ekiNum);

	const int geta = 200000;
	int shitenTime = 0;
	int syutenTime = INF;
	timeCmp.emplace_back(shitenTime);	// 始点の時間
	timeCmp.emplace_back(syutenTime);	// 終点の時間
	REP(i, ekiNum - 1) {
		int trainNum;
		cin >> trainNum;
		totalTrainNum += trainNum;
		REP(j, trainNum) {
			int x, y, c;
			cin >> x >> y >> c;
			int startTimeOne = x + 2 * geta * (i + 1);
			int stopTimeOne = y + 2 * geta * (i + 2);
			trainInfo stOne = {startTimeOne, stopTimeOne, c};
			ekiTimeList[i].emplace_back(startTimeOne);
			ekiTimeList[i + 1].emplace_back(stopTimeOne);
			stTrainInfo[i].emplace_back(stOne);
			timeCmp.emplace_back(startTimeOne);
			timeCmp.emplace_back(startTimeOne + geta);
			timeCmp.emplace_back(stopTimeOne);
			timeCmp.emplace_back(stopTimeOne + geta);
		}
	}
	int classNum;
	cin >> classNum;

	// 重複は削除
	for (auto &ekiTimeOne : ekiTimeList) {
		sort(ekiTimeOne.begin(), ekiTimeOne.end());
		ekiTimeOne.erase(unique(ekiTimeOne.begin(), ekiTimeOne.end()), ekiTimeOne.end());
	}

	// 時間軸をインデックスに圧縮
	map<int, int> T2IDX = compressVectorToMap<int>(timeCmp);

	/*
				駅1			駅2					…	駅n			
				本物		本物	 ダミー					
		始点 -	出発1-1	→	到着1-1→到着1-1				
				出発1-2	→	到着1-2→到着1-2				
				出発1-3	→	到着1-3→到着1-3
									 出発2-1 	…	到着n 
									 出発2-2 	…	到着n 
									 出発2-3 	…	到着n - 終点

		※本物からダミーへは一人だけ
		※ダミー間は遅い時間帯へはいくらでも移動可能
		※時間を枝にするとメモリ足りないので圧縮。
		　ただし、それだと違う駅の時間が同一の値になってしまうので、下駄をはかしている。
	*/
	MinCostFlow res(T2IDX.size());
	
	// 始点→駅1の電車(出発)
	for (auto trainOne : stTrainInfo[0]) {
		res.AddEdge(T2IDX[shitenTime], T2IDX[trainOne.startTime + geta], 1, 0);
	}
	// 駅1(出発)→駅2(到着)の電車
	for (auto trainOne : stTrainInfo[0]) {
		res.AddEdge(T2IDX[trainOne.startTime + geta], T2IDX[trainOne.stopTime], 1, trainOne.cost);
	}

	// 駅2～駅n
	for (int i = 1; i < kukanNum; i++) {
		// 駅i →ダミー駅i
		// 時間一致した場合一人だけの模擬
		for (auto ekiTimeOne : ekiTimeList[i]) {
			res.AddEdge(T2IDX[ekiTimeOne], T2IDX[ekiTimeOne + geta], 1, 0);
		}

		// ダミー駅→ダミー駅
		// 同じ駅には一緒に待てるの模擬
		for (auto ekiFrom : ekiTimeList[i]) {
			for (auto ekiTo : ekiTimeList[i]) {
				if (ekiFrom < ekiTo) {
					res.AddEdge(T2IDX[ekiFrom + geta], T2IDX[ekiTo + geta], classNum, 0);
				}
			}
		}

		// 駅i(出発)→駅i+1(到着)の電車
		auto trainList = stTrainInfo[i];
		for (auto trainOne : trainList) {
			res.AddEdge(T2IDX[trainOne.startTime + geta], T2IDX[trainOne.stopTime], 1, trainOne.cost);
		}
	}

	// 駅n(到着)→終点
	for (auto ekiTime : ekiTimeList[ekiNum - 1]) {
		res.AddEdge(T2IDX[ekiTime], T2IDX[syutenTime], 1, 0);
	}

	res.GetMinCostFlow(T2IDX[shitenTime], T2IDX[syutenTime], classNum);
	cout << res.totalFlowRes << " " << res.totalCostRes << endl;
}

// メイン
int main()
{
	int n;
	
	while (1) {
		cin >> n;
		if (0 == n) {
			break;
		}
		execOne(n);
	}

	return 0;
}

