Claire is a man-eater. She's a real man-eater. She's going around with dozens of guys. She's dating all the time. And one day she found some conflicts in her date schedule. D'oh!

So she needs to pick some dates and give the others up. The dates are set by hours like 13:00 to 15:00. She may have more than one date with a guy. For example, she can have dates with Adam from 10:00 to 12:00 and from 14:00 to 16:00 and with Bob from 12:00 to 13:00 and from 18:00 to 20:00. She can have these dates as long as there is no overlap of time. Time of traveling, time of make-up, trouble from love triangles, and the likes are not of her concern. Thus she can keep all the dates with Adam and Bob in the previous example. All dates are set between 6:00 and 22:00 on the same day.

She wants to get the maximum amount of satisfaction in total. Each guy gives her some satisfaction if he has all scheduled dates. Let's say, for example, Adam's satisfaction is 100 and Bob's satisfaction is 200. Then, since she can make it with both guys, she can get 300 in total. Your task is to write a program to satisfy her demand. Then she could spend a few hours with you... if you really want.



Input

The input consists of a sequence of datasets. Each dataset has the following format:

N
Guy1
...
GuyN


The first line of the input contains an integer N (1 ≤ N ≤ 100), the number of guys. Then there come the descriptions of guys. Each description is given in this format:

M L
S1 E1
...
SM EM


The first line contains two integers Mi (1 ≤ Mi ≤ 16) and Li (1 ≤ Li ≤ 100,000,000), the number of dates set for the guy and the satisfaction she would get from him respectively. Then M lines follow. The i-th line contains two integers Si and Ei (6 ≤ Si < Ei ≤ 22), the starting and ending time of the i-th date.

The end of input is indicated by N = 0.

Output

For each dataset, output in a line the maximum amount of satisfaction she can get.

Example

Input

2
2 100
10 12
14 16
2 200
12 13
18 20
4
1 100
6 22
1 1000
6 22
1 10000
6 22
1 100000
6 22
16
1 100000000
6 7
1 100000000
7 8
1 100000000
8 9
1 100000000
9 10
1 100000000
10 11
1 100000000
11 12
1 100000000
12 13
1 100000000
13 14
1 100000000
14 15
1 100000000
15 16
1 100000000
16 17
1 100000000
17 18
1 100000000
18 19
1 100000000
19 20
1 100000000
20 21
1 100000000
21 22
0


Output

300
100000
1600000000
#include <iostream> // ★
#include <algorithm> // max
#include <cstring> // memset
using namespace std; // ★

#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<n;i++)

int N,date[111],point[111]; // 男の数、各男のデートの時間帯、各男の満足度
int dp[111][1<<16]; // Dynamic Programming で使うメモ。
					// 関数 f(cur,mask) の返り値を dp[cur][mask]に保存する。
					// 男は100人までだが、cur=100もありうるので1つ目の[]の中は101以上必要

// 【デート日程の整数での表し方】
// 例1: 000000000000111(2進数) は「6時〜9時」の意味
// 例2: 000011110011000(2進数) は「10時〜12時と14時〜18時」の意味
// 最下位の桁が6時〜7時、最上位の桁が21時〜22時に対応

int f(int cur,int mask){
	// cur番以降の男とだけデートするとき、maskの時間帯で得られる最大の満足度
	// (番号は0番〜N-1番。ただし、cur=Nもありうる)
	int& res=dp[cur][mask]; // 答えをメモする場所
	if(res>-1)return res; // メモに書かれている数が-1でなかった
						  // = すでに計算されていた。メモされた返り値を返して終了
	
	// ここまで来た場合、関数 f(cur,mask) が呼ばれたのは初めて。
	// 最大の満足度を計算し、その結果を dp[cur][mask] (res) に書き込む
	if(cur==N)return res=0; // N番以降には誰もいないので、誰ともデートできない
							// メモに0と書き、0を返して終了
	
	// ここまで来た場合、cur番の男が実在する。
	// 選択肢1.「cur番の男とデートしない」
	// 選択肢2.「cur番の男とデートする」(maskがcur番の男のデート日程を含んでいる場合のみ)
	res=f(cur+1,mask);
	// 選択肢1。この場合、「cur+1番以降の男とデートして得られる最大の満足度」を得る。
	// 結果はメモに書き込んでおく
	if((date[cur]&mask)==date[cur]){ // mask は date[cur] を含むか？
		res=max(res,point[cur]+f(cur+1,mask^date[cur]));
		// 選択肢2。この場合、「cur番の男の満足度」+
		// 「残った時間帯でcur+1番以降の男とデートして得られる最大の満足度」を得る。
		
		// max(a,b) でaとbのうち大きい方が返る。
		// 選択肢2の結果が現在のメモの値(選択肢1の結果)を上回ったら、メモを上書きする
	}
	return res; // ここでメモに書き込まれているのが最大の満足度。それを返す
}

int main(){
	while(cin>>N && N){ // Nに0が入力されるまで続ける
		rep(i,N){
			int M; // デート回数
			cin>>M>>point[i];
			date[i]=0; // デートの時間帯を初期化
			rep(j,M){
				int S,E; // 開始時刻、終了時刻
				cin>>S>>E;
				rep2(k,S,E)date[i]|=1<<(k-6);
				// 例: S=10, E=13なら, 
				// 下から(10-6=)4番目、5番目、6番目のビットを1にする
			}
		}
		memset(dp,-1,sizeof(dp)); // 配列dpの要素をすべて-1に
		cout<<f(0,(1<<16)-1)<<endl;
		// 答えは「0番以降の男とデートするとき、6時〜22時の間に得られる最大の満足度」。
		// 1111111111111111(2進数,16桁) = 2^16 - 1
	}
}