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 <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define elnd endl //* missspell check
const ll INF = 1LL << 60;

struct edge{ ll to, cap, cost, rev;};

void add_edge(vector<vector<edge> > &G, ll from, ll to, ll cap, ll cost){
    G[from].push_back((edge){to, cap,  cost, (ll)G[to].size()});
    G[to].push_back  ((edge){from, 0, -cost, (ll)G[from].size() - 1});
}
//* minimum cost flow using Bellman-Ford
//* Graph G, source s, sink t, with target flow f
//* returns minimum cost
//* returns -1 if impossible to compute required flow
ll minCostFlowBellmanFord(vector<vector<edge> > &G, ll s, ll t, ll f){
    ll N = G.size();
    vll dist(N); //* dist: shortest distance
    vll prev_v(N), prev_e(N);//* prev_v/prev_e: previous vertex/edge to record shortest path
    
    ll res = 0;
    while( f > 0){
        //* Bellman-Ford to calculate s-t shortest path
        fill(ALL(dist), INF);
        dist[s]=0;
        bool update = true;
        while(update){
            update = false;
            REP(v, N){
                if( dist[v] == INF) continue;
                REP(i, G[v].size()){
                    edge &e = G[v][i];
                    if(e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
                        dist[e.to] = dist[v] + e.cost;
                        prev_v[e.to] = v;
                        prev_e[e.to] = i;
                        update = true;
                    }
                }
            }
        }
        
        if(dist[t] == INF){ //* s is disconnected from t, meaning f is not reachable
            return -1;
        }
        //* run flow as many as possible along shortest path
        ll d = f;
        for(ll v = t; v != s; v = prev_v[v]){
            //* v --> prev_v[v] via prev_e[v]
            d = min(d, G[prev_v[v]][prev_e[v]].cap);
        }
        f -= d;
        res += d * dist[t];
        //* update residual graph along shortest path
        for(ll v = t; v != s; v = prev_v[v]){
            edge &e = G[prev_v[v]][prev_e[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return res;        
}

//! minimum cost flow using Dijkstra, the initial graph should contains NO negative edge
//* Graph G, source s, sink t, with target flow f
//* returns minimum cost
//* returns -1 if impossible to compute required flow
pll minCostFlowDijkstra(vector<vector<edge> > &G, ll s, ll t, ll f){
    ll N = G.size();
    vll dist(N); //* dist: shortest distance
    vll prev_v(N), prev_e(N);//* prev_v/prev_e: previous vertex/edge to record shortest path
    vll h(N); //* potential for each vertex
    
    ll res = 0;
    fill(ALL(h), 0);
    while( f > 0){
        //* Use Dijkstra to update potential h
        priority_queue<pll, vector<pll>, greater<pll> > que;
        fill(ALL(dist), INF);
        dist[s]=0;
        que.push(pll(0, s));
        while(!que.empty()){
            pll p = que.top(); que.pop();
            ll v = p.second;
            if(dist[v] < p.first) continue;
            REP(i, G[v].size()){
                edge &e = G[v][i];
                if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prev_v[e.to] = v;
                    prev_e[e.to] = i;
                    que.push(pll(dist[e.to], e.to));
                }
            }
        }
        
        if(dist[t] == INF){ //* s is disconnected from t, meaning f is not reachable
            // return -1;
            //! customized for this problem
            return pll(res, f);
        }
        REP(v, N) h[v] += dist[v];
        //* run flow as many as possible along shortest path
        ll d = f;
        for(ll v = t; v != s; v = prev_v[v]){
            //* v --> prev_v[v] via prev_e[v]
            d = min(d, G[prev_v[v]][prev_e[v]].cap);
        }
        f -= d;
        res += d * h[t];
        //* update residual graph along shortest path
        for(ll v = t; v != s; v = prev_v[v]){
            edge &e = G[prev_v[v]][prev_e[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return pll(res, 0);
}

struct train{ ll x, y, c;};

int main(){
    while(1){
        ll n; cin >> n;
        if(n == 0)
            break;
        
        vector<vector<train> > rawData(n-1);
        REP(i, n-1){
            ll m; cin >> m;
            REP(j, m){
                ll x, y, c; cin >> x >> y >> c;
                rawData[i].push_back((train){x, y, c});
            }
        }
        ll g; cin >> g;

        vector<set<pll>> dataNode(n-1);
        REP(i, n-1){
            set<pll> arrTime;
            for(auto obj: rawData[i]){
                arrTime.insert(pll(i, obj.y));
            }
            dataNode[i] = arrTime;
        }
        map<pll, ll> nodeToIdx;
        map<ll, pll> idxToNode;
        ll num_vertex = 1;
        REP(i, n-1){
            auto arrTime = dataNode[i];
            for(auto obj: arrTime){
                nodeToIdx[obj] = num_vertex;
                idxToNode[num_vertex] = obj;
                num_vertex += 2;
            }
        }
        num_vertex ++;
        vector<vector<edge> > G(num_vertex);

        REP(i, n-1){
            if(i == 0){
                for(auto data: rawData[i]){
                    ll idx = nodeToIdx[pll(0, data.y)];
                    add_edge(G, 0, idx, 1, data.c);
                }
            }
            else{
                for(auto data: rawData[i]){
                    ll idx = nodeToIdx[pll(i, data.y)];
                    for(auto data_from: dataNode[i-1]){
                        if(data_from.second <= data.x){
                            ll idx_from = nodeToIdx[pll(i-1, data_from.second)];
                            add_edge(G, idx_from+1, idx, 1, data.c);

                        }
                    }
                }
            }
        }
        for(ll v = 1; v < num_vertex-1; v+=2){
            add_edge(G, v, v+1, 1, 0);
        }

        for(auto node: dataNode.back()){
            ll idx = nodeToIdx[node];
            add_edge(G, idx, num_vertex-1, 1, 0);
        }

        pll ans = minCostFlowDijkstra(G, 0, num_vertex-1, g);
        cout<< g - ans.second <<" " << ans.first<<endl;
        

    }


    return 0;
}
