Problem:


Problem B: 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 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.

Sample 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 for the Sample Input

300
100000
1600000000



Sample 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


Sample output:
300
100000
1600000000

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
while 1:
    n = int(raw_input())
    if n == 0: break
    L = [0]*n
    D = [0]*n
    for man in xrange(n):
        m,l = map(int,raw_input().split())
        L[man] = l
        t = 0
        for date in xrange(m):
            s,e = map(int,raw_input().split())
            t ^= ((1 << (e-6))-1) ^ ((1 << (s-6))-1)
        D[man] = t
    dp = [defaultdict(int) for i in xrange(n)]
    dp[0][D[0]] = L[0]
    for i in xrange(1,n):
        for bit in dp[i-1].keys():
            if bit&D[i] == 0:
                dp[i][bit|D[i]] = max(dp[i][bit|D[i]], dp[i-1][bit]+L[i])
        dp[i][D[i]] = max(dp[i][D[i]], L[i])
    ans = 0
    for i in xrange(n):
        ans = max(v for k,v in dp[i].iteritems())
    print ans

Submission status: Accepted

Solution code:
from collections import defaultdict
while 1:
    n = int(raw_input())
    if n == 0: break
    L = [0]*n
    D = [0]*n
    for man in xrange(n):
        m,l = map(int,raw_input().split())
        L[man] = l
        t = 0
        for date in xrange(m):
            s,e = map(int,raw_input().split())
            for s in xrange(s-6,e-6):
                t |= 1 << s
        D[man] = t

    dp = [defaultdict(int) for i in xrange(n)]
    dp[0][D[0]] = L[0]
    for i in xrange(1,n):
        for bit in dp[i-1].keys():
            if bit&D[i] == 0:
                dp[i][bit|D[i]] = max(dp[i][bit|D[i]], dp[i-1][bit]+L[i])
            dp[i][bit] = max(dp[i][bit],dp[i-1][bit])
        dp[i][D[i]] = max(dp[i][D[i]], L[i])
        
    ans = max(max(dp[i].values()) for i in xrange(n))
    print ans

Submission status: Accepted

Solution code:
from collections import defaultdict
while 1:
    n = int(raw_input())
    if n == 0: break
    L = [0]*n
    T = [0]*n
    for man in xrange(n):
        m,l = map(int,raw_input().split())
        L[man] = l
        t = 0
        for date in xrange(m):
            s,e = map(int,raw_input().split())
            t |= 2**(e-6)-2**(s-6)
        T[man] = t

    dp = defaultdict(int)
    dp[T[0]] = L[0]
    for i in xrange(1,n):
        for bit in dp.keys():
            if bit&T[i] == 0:
                dp[bit|T[i]] = max(dp[bit|T[i]], dp[bit]+L[i])
        dp[T[i]] = max(dp[T[i]], L[i])
        
    print max(dp.values())

Submission status: Accepted

Solution code:
from collections import defaultdict
while 1:
    n = int(raw_input())
    if n == 0: break
    L = [0]*n
    T = [0]*n
    for man in xrange(n):
        m,l = map(int,raw_input().split())
        L[man] = l
        t = 0
        for date in xrange(m):
            s,e = map(int,raw_input().split())
            t |= 2**(e-6)-2**(s-6)
        T[man] = t

    dp = defaultdict(int)
    for l,t in zip(L,T):
        for bit in dp.keys():
            if bit&t == 0:
                dp[bit|t] = max(dp[bit|t], dp[bit]+l)
        dp[t] = max(dp[t], l)
        
    print max(dp.values())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()
        if n == 0:
            break
        ms = []
        for _ in range(n):
            m,l = LI()
            a = [LI() for _ in range(m)]
            b = 0
            for s,e in a:
                for i in range(s,e):
                    b |= 2**(i-6)
            ms.append((l,b))

        d = collections.defaultdict(int)
        d[0] = 0
        for l,b in ms:
            for k,v in list(d.items()):
                if b&k > 0:
                    continue
                if d[b|k] < v + l:
                    d[b|k] = v + l
        rr.append(max(d.values()))

    return '\n'.join(map(str, rr))


print(main())

Submission status: Runtime Error

Solution code:
while 1:
    n = int(raw_input())
    if n == 0: break
    L = [0]*n
    D = [0]*n
    for man in xrange(n):
        m,l = map(int,raw_input().split())
        L[man] = l
        t = 0
        for date in xrange(m):
            s,e = map(int,raw_input().split())
            t ^= ((1 << (e-6))-1) ^ ((1 << (s-6))-1)
        D[man] = t
    dp = [[0]*(1 << 17) for i in xrange(n)]
    dp[0][D[0]] = L[0]
    for i in xrange(1,n):
        for bit in xrange(1 << 17):
            if dp[i-1][bit] and bit&D[i] == 0:
                dp[i][bit|D[i]] = max(dp[i][bit|D[i]], dp[i-1][bit]+L[i])
        dp[i][D[i]] = max(dp[i][D[i]], L[i])
    print max(max(dp[i]) for i in xrange(n))

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()
        if n == 0:
            break
        ms = []
        for _ in range(n):
            m,l = LI()
            a = [LI() for _ in range(m)]
            b = []
            for s,e in a:
                f = 0
                for i in range(s,e):
                    f |= 2**(i-6)
                b.append(f)
            ms.append((l,b))

        d = collections.defaultdict(int)
        d[0] = 0
        for l,b in ms:
            g = collections.defaultdict(int)
            for k,v in d.items():
                for f in b:
                    if f&k > 0:
                        continue
                    if g[f|k] < v + l:
                        g[f|k] = v + l
            for k,v in g.items():
                if d[k] < v:
                    d[k] = v
        rr.append(max(d.values()))

    return '\n'.join(map(str, rr))


print(main())