Butterfly

Time limit8sMemory limit512 MB

Summary

Choose non-overlapping dates; each person pays only if all their dates are kept, so maximize total satisfaction.

Level: Medium7 of 10
Topics: Intervals, Dynamic programming, Bit manipulation, Greedy
Solved: No attempts yet

Problem

Claire books several dates in one day. She sees dozens of people, and one day her schedule collided with itself.

Every date is fixed by clock hours, like 13:00 to 15:00, and all dates fall between 6:00 and 22:00 on the same day. She can book more than one date with the same person. Suppose she has dates with Adam from 10:00 to 12:00 and from 14:00 to 16:00, and dates with Bob from 12:00 to 13:00 and from 18:00 to 20:00. None of the four overlap, so she can keep all of them. Travel time, time to do her makeup, and trouble from love triangles do not matter here. A date that starts exactly when another one ends does not overlap it.

Person $i$ gives her satisfaction $L_i$ only when every date booked with that person is kept. If she gives up even one of them, she gets nothing from him. In the example above, Adam's satisfaction is 100 and Bob's is 200, and she keeps both, so the total is 300.

Two dates booked with the same person can also overlap each other. Keeping all of them is then impossible, so the satisfaction from that person is 0.

Choose the dates to keep and report the largest total satisfaction Claire can get.

Input

The input holds several datasets. Each dataset has this format:

N
person 1
...
person N

The first line has the number of people $N$ ( $1 \le N \le 100$ ). The descriptions of the $N$ people follow in order, each in this format:

M L
S1 E1
...
SM EM

The first line has the number of dates $M$ ( $1 \le M \le 16$ ) booked with that person and the satisfaction $L$ ( $1 \le L \le 10^8$ ) he gives her. Each of the next $M$ lines has the start time $S$ and the end time $E$ of one date ( $6 \le S < E \le 22$ ). All input values are integers.

A line holding 0 in place of $N$ ends the input. That line is not a dataset.

Output

For each dataset, print the largest total satisfaction Claire can get on one line.

Examples2

Example 1

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

Expected output

300
100000
1600000000

Example 2
Input
```
1
1 42
6 22
0
```
Expected output
```
42
```