Problems
Butterfly
Butterfly
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 \textbf{13:00} to \textbf{15:00}. She may have more than one date with a guy. For example, she can have dates with Adam from \textbf{10:00} to \textbf{12:00} and from \textbf{14:00} to \textbf{16:00} and with Bob from \textbf{12:00} to \textbf{13:00} and from \textbf{18:00} to \textbf{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 \textbf{6:00} and \textbf{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 \textbf{100} and Bob's satisfaction is \textbf{200}. Then, since she can make it with both guys, she can get \textbf{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.
\InputFile
The input consists of a sequence of datasets. Each dataset has the following format:
\textbf{N Guy_1 ... Guy_N}
The fi rst line of the input contains an integer \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}), the number of guys. Then there come the descriptions of guys. Each description is given in this format:
\textbf{M L S_1 E_1 ... S_M E_M}
The first line contains two integers \textbf{M_i} (\textbf{1} ≤ \textbf{M_i} ≤ \textbf{16}) and \textbf{L_i} (\textbf{1} ≤ \textbf{L_i} ≤ \textbf{100000000}), the number of dates set for the guy and the satisfaction she would get from him respectively. Then \textbf{M} lines follow. The \textbf{i}-th line contains two integers \textbf{S_i} and \textbf{E_i} (\textbf{6} ≤ \textbf{S_i} < \textbf{E_i} ≤ \textbf{22}), the starting and ending time of the \textbf{i}-th date.
The end of input is indicated by \textbf{N = 0}.
\OutputFile
For each dataset, output in a line the maximum amount of satisfaction she can get.
Input example #1
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 example #1
300 100000 1600000000