Problem:
 Score : 300 points    Problem Statement There are N people numbered 1 to N . Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.  Person i gives A_i testimonies. The j -th testimony by Person i is represented by two integers x_{ij} and y_{ij} . If y_{ij} = 1 , the testimony says Person x_{ij} is honest; if y_{ij} = 0 , it says Person x_{ij} is unkind.  How many honest persons can be among those N people at most?      Constraints  All values in input are integers.  1 \leq N \leq 15  0 \leq A_i \leq N - 1  1 \leq x_{ij} \leq N  x_{ij} \neq i  x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)  y_{ij} = 0, 1         Input Input is given from Standard Input in the following format:  N  A_1  x_{11}  y_{11}  x_{12}  y_{12}  :  x_{1A_1}  y_{1A_1}  A_2  x_{21}  y_{21}  x_{22}  y_{22}  :  x_{2A_2}  y_{2A_2}  :  A_N  x_{N1}  y_{N1}  x_{N2}  y_{N2}  :  x_{NA_N}  y_{NA_N}       Output Print the maximum possible number of honest persons among the N people.        Sample Input 1 3
1
2 1
1
1 1
1
2 0      Sample Output 1 2  If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.       Sample Input 2 3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0      Sample Output 2 0  Assuming that one or more of them are honest immediately leads to a contradiction.       Sample Input 3 2
1
2 0
1
1 0      Sample Output 3 1

Solution (Python):
N = int(input())
X = []
for _ in range(N):
    a = int(input())
    X.append([[int(a) for a in input().split()] for __ in range(a)])

def chk(m):
    L = [m >> i & 1 for i in range(N)]
    for i in range(N):
        for x, y in X[i]:
            x -= 1
            if L[i] and L[x] != y: return 0
    return 1

ma = 0
for i in range(1<<N):
    if chk(i):
        ma = max(ma, bin(i).count("1"))
print(ma)

Solution (Python):
n = int(input())

e = [[] for _ in range(n)]

for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        x -= 1
        e[i].append((x, y))

ret = 0
for mask in range(1 << n):
    t = [(mask >> i) & 1 for i in range(n)]
    flg = True
    for i in range(n):
        if t[i]:
            for x, y in e[i]:
                if t[x] != y:
                    flg = False
                    break
            if not flg:
                break
    if flg:
        ret = max(ret, sum(t))

print(ret)

Solution (Python):
N = int(input())

M = []
for _ in range(N):
    A = int(input())
    state = []
    for _ in range(A):
        x, y = map(int, input().split())
        x -= 1
        state.append((x, y))
    M.append(state)

ans = 0
for mask in range(1 << N):
    can = True
    for i, s in enumerate(M):
        if (mask & (1 << i)) != 0:
            for x, y in s:
                v = 1 if (mask & (1 << x)) != 0 else 0
                if v != y:
                    can = False
                    break
    if can:
        cnt = 0
        for i in range(N):
            if (mask & (1 << i)) != 0:
                cnt += 1
        ans = max(ans, cnt)

print(ans)

Solution (Python):
N=int(input())
A = [None]*N
for i in range(N):
    m = int(input())
    A[i] = [list(map(int,input().split())) for _ in [0]*m]

ans = 0
for i in range(2**N):
    done = [-1]*N
    for j in range(N):
        if (i>>j)&1==0:
            if done[j] == 1: break
            done[j] = 0
            continue
        if done[j] == 0 : break
        done[j] = 1
        breakFlg = False
        for x,y in A[j]:
            x -= 1
            if done[x] == -1:
                done[x] = y
            elif done[x] != y:
                breakFlg = True
                break
        if breakFlg: break
    else:
        tmp = sum(map(int,bin(i)[2:]))
        ans = max(ans,tmp)
print(ans)

Solution (Python):
from itertools import combinations
n = int(input())
l = [[] for _ in range(n)]
for i in range(n):
    for _ in range(int(input())):
        l[i].append(list(map(int, input().split())))

people = list(range(1, n + 1))

for res in people[::-1]:
    for c in combinations(people, res):
        s = set(c)
        valid = True
        for i in c:
            for p, y in l[i - 1]:
                if y == 0:
                    valid &= not p in s
                else:
                    valid &= p in s
            if not valid:
                break
        if valid:
            print(res)
            exit()
print(0)

Solution (Python):
import sys
readline = sys.stdin.readline

def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

N = int(readline())

G = [0]*N
H = [0]*N
for i in range (N):
    A = int(readline())
    for _ in range(A):
        x, y = map(int, readline().split())
        if y == 1:
            G[i] |= 1<<(x-1)
        else:
            H[i] |= 1<<(x-1)

ans = 0

for s in range(1<<N):
    for i in range(N):
        if (1<<i) & s:
            g, h = G[i], H[i]
            if g != (g&s):
                break
            if h != (h&(~s)):
                break
            
    else:
        ans = max(ans, popcount(s))
print(ans)

Solution (Python):
from itertools import chain, combinations


def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


n = int(input())
x = []
for i in range(n):
    xi = []
    a = int(input())
    for j in range(a):
        xij, yij = map(int, input().split())
        xi.append((xij-1, bool(yij)))
    x.append(xi)

res = 0
for cands in powerset(range(n)):
    cands = set(cands)
    for c in cands:
        flagc = True
        for xc, yc in x[c]:
            if yc != (xc in cands):
                flagc = False
                break
        if not flagc:
            break
    else:
        res = max(len(cands), res)
print(res)

Solution (Python):
N = int(input())
from collections import  defaultdict
items = defaultdict(list)
for i in range(N):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        x-=1
        items[i].append([x, y])

ans = 0
for bit in range(2 ** N):
    tmp = [False] * N
    cnt = 0
    for k in range(N):
        if bit & (1 << k):
            tmp[k] = True
            cnt += 1
    
    check = True
    for k in range(N):
        if tmp[k]:
            res = items[k]
            for r in res:
                x = r[0]
                y = r[1]
                if y == 1:
                    if tmp[x]:
                        continue
                    else:
                        check = False
                else:
                    if tmp[x]:
                        check = False
                    else:
                        continue
    if check:
        ans = max(ans, cnt)
print(ans)

Solution (Python):
import itertools
n=int(input())
l=[[] for i in range(n)]
for i in range(n):
    m=int(input())
    for j in range(m):
        l[i].append(list(map(int,input().split())))
ans=0
it=list(itertools.product([0,1],repeat=n))
for i in it:
    tmp=[]
    for num,j in enumerate(i):
        if j==1:
            for k in l[num]:
                tmp.append(k)
    if all (i[j[0]-1]==j[1] for j in tmp):ans=max(ans,sum(i))
print(ans)

Solution (Python):
N=int(input())
arr = [[] for i in range(N+1)]
bm = [0 for i in range(N+1)]
maxs = 0
cnt = 0

def slv(curInd):
  global N,arr,bm,maxs,cnt
  if curInd==N:
    good = True
    for i in range(N+1):
      if good == False:
        break
      if bm[i]:
        for el in arr[i]:
          if bm[el[0]]!=el[1]:
            good = False
            break
    if good == True:
      maxs = max(maxs,cnt)
    cnt += 1
    bm[curInd] = 1
    good = True
    for i in range(N+1):
      if good == False:
        break
      if bm[i]:
        for el in arr[i]:
          if bm[el[0]]!=el[1]:
            good = False
            break
    if good == True:
      maxs = max(maxs,cnt)
    bm[curInd] = 0
    cnt -= 1
  else:
    slv(curInd+1)
    cnt += 1
    bm[curInd] = 1
    slv(curInd+1)
    cnt -= 1
    bm[curInd] = 0

for i in range(N):
  A=int(input())
  for j in range(A):
    arr[i+1].append(list(map(int,input().split())))
slv(1)
print(maxs)

Solution (Python):
N = int(input())
a = [[] for i in range(N)]
for i in range(N):
	A = int(input())
	for j in range(A):
		x,y = map(int,input().split())
		a[i].append((x-1,y))

def int2bit(n):
	ret = [0 for i in range(N)]
	i = 0
	while n > 0:
		ret[i] = n % 2
		n = n // 2
		i += 1
	return ret

ans = 0
for i in range(2**N - 1, -1, -1):
	bit = int2bit(i)
	flg = True
	for n in range(N):
		if bit[n] == 0:
			continue
		for x in a[n]:
			if bit[x[0]] != x[1]:
				flg = False
				break
		if not flg:
			break
	if flg:
		ans = max(ans, sum(bit))
print(ans)

Solution (Python):
N = int(input())
Axyss = []
for i in range(N):
  A = int(input())
  xys = []
  for j in range(A):
    x, y = map(int, input().split())
    x = x-1
    xys.append((x, y))
  Axyss.append((A, xys))
r = 0
for n in range(2**N):
  ss = [0]*N
  for i in range(N):
    if n&(1<<i) != 0:
      ss[i] = 1
  c = ss.count(1)
  if c <= r:
    continue
  ok = True
  for i in range(N):
    s = ss[i]
    A, xys = Axyss[i]
    for x, y in xys:
      if s == 1 and ss[x] != y:
        ok = False
        break
  if ok:
    r = max(r, c)
print(r)

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N = int(sys.stdin.buffer.readline())
XY = []
for _ in range(N):
    a = int(sys.stdin.buffer.readline())
    xy = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(a)]
    XY.append([(x - 1, y) for x, y in xy])

ans = 0
for choice in itertools.product([0, 1], repeat=N):
    ok = True
    for i in range(N):
        if choice[i] == 0:
            continue
        
        for x, y in XY[i]:
            ok &= (choice[x] == y) == choice[i]
    if ok:
        ans = max(ans, sum(choice))
print(ans)

Solution (Python):
N = int(input())
A = [0] * N
xy = [[] for _ in range(N)]
for i in range(N):
  A[i] = int(input())
  xy[i] = [list(map(int, input().split())) for _ in range(A[i])]
  
def nasu(n):
  D = [0] * N
  x = n
  for i in range(N):
    if x & 1:
      D[i] = 1
    x >>= 1
  for i in range(N):
    if D[i] == 0: continue
    for j in range(A[i]):
      if D[xy[i][j][0] - 1] != xy[i][j][1]:
        return False
  return True

ans = 0
for i in range(1, N + 1):
  n = (1 << i) - 1
  while n < (1 << N):
    if nasu(n):
      ans = i
      break
    x = n & -n
    y = n + x
    n = ((n & ~y) // x >> 1) | y
    
print(ans)

Solution (Python):
import math

def makelist(n, m):
    return [[[] for _ in range(m)] for _ in range(n)]






N = int(input())
A = [0]*(N+1)
x = [[] for _ in range(N+1)]
for i in range(1, N+1):
    A[i] = int(input())
    for _ in range(A[i]):
        a, b = list(map(int, input().split()))
        x[i].append((a, b))

ans = 0
for i in range(1<<N):
    dp = [False]*(N+1)
    flag = True

    ind = 1
    hoge = i
    while i > 0:
        if i % 2 == 1:
            dp[ind] = True
            
        ind += 1
        i //= 2

    
    for i in range(1, N+1):
        if dp[i]:
            for (a, b) in x[i]:
                if b == 1:
                    if not dp[a]:
                        flag = False
                        break
                elif b == 0:
                    if dp[a]:
                        flag = False
                        break
        if not flag:
            break
        

    if flag:
        ans = max(ans, dp.count(True))
print(ans)

Solution (Python):
N = int(input())
data = []
for _ in range(N):
    M = int(input())
    XY = [list(map(int, input().split())) for _ in range(M)]
    data.append((M, XY))

ans = 0
for bit in range(2**N):
    ok = True
    P = [-1]*N
    c = 0
    for i in range(N):
        M, XY = data[i]
        if bit & (1<<i):
            c += 1
            if P[i] == 0:
                ok = False
                break
            P[i] = 1
            for x, y in XY:
                if P[x-1] == -1:
                    P[x-1] = y
                elif P[x-1] != y:
                    ok = False
                    break
        else:
            if P[i] == 1:
                ok = False
            P[i] = 0
    if ok:
        ans = max(ans, c)
print(ans)

Solution (Python):


import itertools


def max_honests(n, statements):
    g = itertools.product((True, False), repeat=n)
    res = 0
    for is_hon in g:
        flag = True
        for i in range(n):
            if is_hon[i]:
                for x, y in statements[i]:
                    if is_hon[x] != y:
                        flag = False
        if flag:
            res = max(res, sum(is_hon))
    return res


def main():
    n = int(input())
    statements = [set() for _ in range(n)]
    for i in range(n):
        a = int(input())
        for _ in range(a):
            x, y = (int(z) for z in input().split())
            statements[i].add((x - 1, bool(y)))
    res = max_honests(n, statements)
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):



import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

n = int(input())


shogen = [None for _ in range(n)]

for i in range(n):
    c = int(input())
    g = []
    for _ in range(c):
        p,q = [int(i) for i in readline().split()]
        g.append([p-1,q])
    
    
    shogen[i] = g


def check(mask):
    cnt = 0
    for i in range(n):
        if mask & (1<<i):
            cnt += 1
            for (p,TF) in shogen[i]:
                if mask&(1<<p) != TF<<p:
                    return 0
            
    
    return cnt
    

N = 2**n
ans = 0
for mask in range(N):
    c = check(mask)
    
    ans = max(ans,c)    

print(ans)

Solution (Python):
n = int(input())
shogens = []

for i in range(n):
    a = int(input())
    shogens.append([])
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        shogens[-1].append((x,y))

def is_honest(i, j):
    return (i >> j) % 2 == 1

def honest_cnt(i):
    ans = 0
    for j in range(n):
        ans += is_honest(i, j)
    return ans

ans = 0

for i in range(1 << n):
    ok = True
    for j in range(n):
        if not is_honest(i,j):continue
        for (x, y) in shogens[j]:
            if y == 0 and is_honest(i, x):ok = False
            if y == 1 and not is_honest(i, x):ok = False
    if ok:
        ans = max(ans, honest_cnt(i))

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[None]*n
    for i in range(n):
        a=int(input())
        XY=[tuple(map(int,input().split())) for _ in range(a)]
        E[i]=XY

    N=2**n
    ans=0
    for S in range(N):
        flag=True
        for i in range(n):
            if((S>>i)&1)==0: continue 
            for x,y in E[i]:
                x-=1
                if((S>>x)&1)!=y:
                    flag=False
        if(flag):
            ans=max(ans,bin(S).count('1'))
    print(ans)
resolve()

Solution (Python):
N = int(input())
data = []
for _ in range(N):
	A = int(input())
	items = []
	for __ in range(A):
		x, y = map(int, input().split())
		items.append((x - 1, y))
	data.append(items)


best = 0

def check(state):
	for i in range(N):
		if state[i] == 1:
			for x, y in data[i]:
				if y != state[x]:
					return False
	return True

def combination(state):
	global best
	if len(state) == N:
		if check(state):
			count = sum(state)
			if count > best:
				best = count
	else:
		combination(state + [0])
		combination(state + [1])

combination([])

print(best)

Solution (Python):
n = int(input())
from collections import defaultdict
dic = defaultdict(list)

for i in range(n):
    a = int(input())
    for _ in range(a):
        x,y = map(int,input().split())
        dic[i].append((x-1,y))
    

ans = 0
for i in range(2 ** n):
    bit = [0] * n
    for j in range(n):
        if ((i >> j) & 1):
            bit[j] = 1
    
    for idx, b in enumerate(bit):
        if b == 1:
            for x,y in dic[idx]:
                if bit[x] != y:
                    break
            else:
                continue
            break
    else:
        ans = max(ans, sum(bit))

print(ans)

Solution (Python):
n=int(input())
l=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        l[i].append([x,y])
op=['0','1']
for i in range(n-1):
    tmp=[]
    for j in op:
        tmp.append(j+'0')
        tmp.append(j+'1')
    op=tmp
ans=0
for i in op:
    t=list(i)
    f=0
    for j in range(n):
        if i[j]=='1':
            for k in l[j]:
                if t[k[0]-1]!=str(k[1]):
                    f+=1
    if f==0:
        p=0
        for q in t:
            if q=='1':
                p+=1
        ans=max(ans,p)
print(ans)

Solution (Python):
from itertools import product

N = int(input())


memo = []
for i in range(N):
    a = int(input())
    l = []
    for _ in range(a):
        x,y = map(int,input().split())
        l.append((x-1,y==1))
    memo.append(l)
    
def check(p):
    return all(p[x]==y for i,l in enumerate(memo) for x,y in l if p[i])

m = max(sum(p) for p in product((True,False), repeat=N) if check(p))
print(m)

Solution (Python):
n = int(input())

a = [0] * n
d = [[] for _ in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        d[i].append(tuple(map(int, input().split())))

def decode(s):
    r = [0] * n
    for i in range(n):
        r[i] = int(bool(s & (1 << i)))
    return r

def validate(s):
    r = decode(s)
    for i in range(n):
        if not r[i]:
            continue
        for x, y in d[i]:
            if r[x - 1] != y:
                return 0
    return sum(r)

def solve():
    ans = 0
    for i in range(2 ** n):
        ans = max(ans, validate(i))
    print(ans)

solve()

Solution (Python):
def main():
    n=int(input())
    a=[]
    x=[]
    for i in range(n):
        a.append(int(input()))
        x.append([list(map(int,input().split())) for _ in [0]*a[-1]])
    cnt=0
    for i in range(2**n):
        flag=0
        c=("0"*n+bin(i)[2:])[-n:]
        for i in range(n):
            if c[i]=="0":
                continue
            for j,k in x[i]:
                if (k==1 and c[j-1]=="0") or (k==0 and c[j-1]=="1"):
                    flag=1
                    break
        if flag==1:
            continue
        cnt=max(cnt,c.count("1"))
    print(cnt)
main()

Solution (Python):
n = int(input())
info = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        info[i].append((x, y))

ans = 0
for bit_state in range(1 << n):
    flag = True
    for i in range(n):
        
        if (bit_state >> i) & 1:
            for x, y in info[i]:
                if (bit_state >> x) & 1 != y:
                    flag = False
    if flag:
        ans = max(bin(bit_state).count("1"), ans)
print(ans)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
words = []
for i in range(n):
	a = int(input())
	w = []
	for _ in range(a):
		x, y = map(int, input().split())
		w.append([x-1, y])
	words.append(w)


ans = 0
for bit in range(1<<n):
	ok = True
	is_honest = [(bit>>i) & 1 for i in range(n)]
	
	for i in range(n):
		if not is_honest[i]:
			continue
		for x, y in words[i]:
			if is_honest[x] != y:
				ok = False
	if ok:
		ans = max(ans, sum(is_honest))
print(ans)

Solution (Python):
n = int(input())

g = [[-1 for j in range(n)] for i in range(n)]

for i in range(n):
	a = int(input())
	for _ in range(a):
		x, y = map(int, input().split())
		g[i][x-1] = y

ans = 0
for s in range(2**n):
	ok = True
	for i in range(n):
		if (s>>i&1) == 1:
			for j in range(n):
				if g[i][j] == -1: continue
				if (s>>j&1) != g[i][j]: ok = False
	if ok:
		
		t = 0
		x = s
		while x > 0:
			t += x%2
			x //= 2
		ans = max(ans, t)

print(ans)

Solution (Python):
n = int(input())
data = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        data[i].append(list(map(int,input().split())))


ans = 0
for i in range(1<<n):
    truth = []
    for x in range(n):
        if i&(1<<x):
            truth.append(x+1)

    q = True
    for j in truth:
        for x,y in data[j-1]:
            if x in truth and y == 0:
                q = False
                break
            if x not in truth and y == 1:
                q = False
                break
    if q:
        ans = max(ans,len(truth))
        

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N=int(input())
C=[]
for i in range(N):
    A=int(input())
    B=[tuple(map(int,input().split())) for i in range(A)]
    C.append(B)

ANS=0

for i in range(1<<N):
    HONEST=[j for j in range(N) if 1<<j & i !=0]

    

    flag=1

    for h in HONEST:
        for p,k in C[h]:
            if k==1:
                if p-1 in HONEST:
                    continue
                else:
                    flag=0
                    break

            else:
                if p-1 in HONEST:
                    flag=0
                    break
        if flag==0:
            break

    if flag==1:
        
        ANS=max(ANS,len(HONEST))

print(ANS)

Solution (Python):
N = int(input())
B = [[] for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        B[i].append((x-1, y))
ans = 0
for s in range(1<<N):
    flag1 = True
    cnt = 0
    for i in range(N):
        if s&(1<<i):
            cnt+=1
            flag2 = True
            for x, y in B[i]:
                if ((s>>x)&1) != y:
                    flag2 = False
                    break
            if not flag2:
                flag1 = False
    if flag1:
        ans = max(ans, cnt)
print(ans)

Solution (Python):
n = int(input())

A =[]
for i in range(n):
    m = int(input())
    A.append([list(map(int,input().split())) for i in range(m)])


ans = 0
for i in range(2**n):
    r = 1
    ib = list(format(i, "b").zfill(n))
    
    for j in range(n):
        if ib[j] == "1":
            for k in range(len(A[j])):
                if int(ib[A[j][k][0]-1]) != A[j][k][1]:
                    r = 0
    if r == 1:
        ans = max(ans, ib.count("1"))
print(ans)

Solution (Python):
N = int(input())
data = [[] for _ in range(N)]

for i in range(N):
    Ai = int(input())
    
    for _ in range(Ai):
        xi, yi = map(int, input().split())
        data[i].append((xi-1, yi))
    
ans = 0

for i in range(2**N):
    flag = [False]*N
    ans_cand = 0
    
    for j in range(N):
        if (i>>j)&1:
            flag[j] = True
            ans_cand += 1
    
    F = True
    
    for j in range(N):
        if flag[j]:
            for xi, yi in data[j]:
                if (yi==0 and flag[xi]) or (yi==1 and not flag[xi]):
                    F = False
                    
    if F:
        ans = max(ans, ans_cand)

print(ans)

Solution (Python):
N = int(input())
A = [[] for i in range(N)]
for i in range(N):
  n = int(input())
  for _ in range(n):
    x, y = map(int, input().split())
    A[i].append((x - 1, y))

ans = 0
for i in range(1 << N):
  ok = True
  cnt = 0
  for j in range(N):
    if (i >> j & 1) == 1:
      cnt += 1
  for j in range(N):
    if (i >> j & 1) == 1:
      for x, y in A[j]:
        if y == 0:
          if (i >> x & 1) == 1:
            ok = False
        elif y == 1:
          if (i >> x & 1) == 0:
            ok = False
  if ok:
    ans = max(ans, cnt)

print(ans)