Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

クイズ

あなたはクイズ番組のディレクターである．
クイズ番組には解答者として N 人が出演予定であり，それぞれ 1 から N まで番号付けられている．

問題は M+1 問出題する予定であり，それぞれの問題は 1 から M+1 まで番号付けられている．
問題は番号順に出題され，それぞれ早押しで最初に正解した人にのみ得点が入る．i 問目の問題の得点は整数 Si である．
M+1 問目の問題を終えた時点で総合得点が最大の人が優勝する．
ただし，最大得点の人が複数人存在する場合，優勝者は存在しない．

現在 M 問目まで配点を決めたので，M+1 問目の配点を決めようと考えている． 
最後の問題は，誰でも逆転できる点数にするのがクイズ番組のお約束である． 
しかし，その場で解答者たちの総合得点を見て問題の点数を決めると，解答者たちのやる気を削ぐ可能性がある．そこで， どんな点数状況でも全員に逆転のチャンスがあるような点数設定をあらかじめ考えることにした．

幸い，1 から M 問目まではそれぞれ正解する可能性がある解答者が分かっている．M+1 問目は全員が正解する可能性のある問題である．正解する可能性がある解答者の中で，早押しで正解した1名のみが問題の得点 Si を得る．問題への解答は正解した解答者が現れた時点で締め切られ，同じ解答者は何度でも解答を行うことができるため，ある問題の得点 Si を誰も得られない場合は考慮しなくてよい．また，複数人の解答者がある問題の得点 Si を重複して獲得したり，得点を分け合ったりすることもない． 

各問の配点と正解可能な解答者の情報を基に， 起こりうるどのような得点状況においても，最後の問題を正解すれば必ず誰でも優勝できるように最後の問題の点数 SM+1 を設定したい． 条件を満たす整数 SM+1 として最小の値を求めよ．

Input

入力データセットは複数のケースから構成される．各ケースは次のような形式である．

N M
S1 k1 c1,1 ... c1,k1
...
SM kM cM,1 ... cM,kM

1 行目には，解答者の数 N と最後の問題を除いた問題の個数 M が与えられる．
続く M 行には，問題 1 〜 M についての解答できる可能性のある解答者の情報が与えられる．そのうち i 行目には，i 問目の得点 Si と，i 問目に正解する可能性がある解答者の人数 ki が与えられ，またその直後に ki 個の数 ci,1 ... ci,ki が与えられる．ci,j  (1 ≤ j ≤ ki) はそれぞれ ，i 問目に正解する可能性がある解答者の番号を表す．

入力の終わりは 2 つのゼロからなる行で示す．データセットの個数は最大でも 30 個を超えない．

入力で与えられる数値は全て整数であり，以下の条件を満たす．

 2 ≤ N ≤ 10,000

 1 ≤ M ≤ 1,000

 1 ≤ Si ≤ 100

 1 ≤ ki ≤ N

 1 ≤ ci,1 i,ki ≤ N

 Σki  ≤  100,000

ただし，出力すべき SM+1 はこの範囲を超える場合があることに注意せよ．

Output

各データセットについて条件を満たすような最後の問題の点数 SM+1 の最小値を 1 行に出力せよ．

Sample Input

3 2
5 2 1 3
8 2 2 3
2 3
8 2 1 2
3 1 1
5 1 2
2 5
100 1 1
100 1 1
100 1 1
100 1 1
100 1 1
3 4
5 1 1
5 1 2
100 2 1 3
100 2 2 3
0 0

Output for Sample Input

14
11
501
196



Sample input:
3 2
5 2 1 3
8 2 2 3
2 3
8 2 1 2
3 1 1
5 1 2
2 5
100 1 1
100 1 1
100 1 1
100 1 1
100 1 1
3 4
5 1 1
5 1 2
100 2 1 3
100 2 2 3
0 0


Sample output:
14
11
501
196

Submission status: Accepted

Solution code:
# AOJ 2825: Quiz
# Python3 2018.7.12 bal4u

while True:
	N, M = map(int, input().split())
	if N == 0: break
	mi, ma = [0]*N, [0]*N
	for i in range(M):
		a = list(map(int, input().split()))
		S = a.pop(0)
		K = a.pop(0)
		if K == 1:
			mi[a[0]-1] += S
			ma[a[0]-1] += S
		else:
			for j in a: ma[j-1] += S
	vmax = max(ma)
	mi.pop(ma.index(vmax))
	vmin = min(mi)
	print(vmax-vmin+1)

Submission status: Accepted

Solution code:
def main():
    while(True):
        N, M = map(int, input().split())
        if(N == 0 and M == 0):
            return
        skc = []
        for i in range(M):
            skc.append(list(map(int, input().split())))
        point = [0 for i in range(N)]
        for i in range(M):
            for j in range(2, len(skc[i])):
                point[skc[i][j] - 1] += skc[i][0]
        point_fixed = [0 for i in range(N)]
        for i in range(M):
            if(skc[i][1] == 1):
                point_fixed[skc[i][2] - 1] += skc[i][0]
        maxPlayer = 0
        Max = 0
        for i in range(N):
            if(Max < point[i]):
                Max = point[i]
                maxPlayer = i + 1
        minPlayer = 0
        Min = 1e9
        for i in range(N):
            if(i + 1 == maxPlayer):
                continue
            if(Min > point_fixed[i]):
                Min = point_fixed[i]
                minPlayer = i + 1        
        print(point[maxPlayer - 1] - point_fixed[minPlayer - 1] + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, input().split())
    if n == 0:break
    minp = [0] * (n + 1)
    minp[0] = 1e10
    maxp = [0] * (n + 1)
    for _ in range(m):
        s, k, *c =  map(int, input().split())
        if k == 1:
            minp[c[0]] += s
        for i in range(k):
            maxp[c[i]] += s
    p = list(zip(maxp, minp))
    p.sort(key = lambda x:x[1])
    p.sort(key = lambda x:x[0], reverse = True)
    p.pop()
    s = 0
    for i in range(n - 1):
        if p[i][0] <= s:break
        for j in range(i + 1, n):
            s = max(s, p[i][0] - p[j][1])
    print(s + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

while True:
    N,M = inpl()
    if N == 0 and M == 0:
        break
    else:
        MINlist = [[0,i] for i in range(N)]
        MAXlist = [[0,i] for i in range(N)]
        for _ in range(M):
            arg = inpl()
            s = arg[0]
            k = arg[1]
            cc = arg[2:]
            for c in cc:
                MAXlist[c-1][0] += s
            if k == 1:
                MINlist[c-1][0] += s

        MINlist.sort()
        MAXlist.sort(reverse=True)
        MinVal1,MinId1 = MINlist[0]
        MinVal2,MinId2 = MINlist[1]
        MaxVal1,MaxId1 = MAXlist[0]
        MaxVal2,MaxId2 = MAXlist[1]
        if MinId1 != MaxId1:
            print(MaxVal1-MinVal1+1)
        else:
            print(max(MaxVal2-MinVal1,MaxVal1-MinVal2)+1)

Submission status: Accepted

Solution code:
import sys


def solve(n, m, s, k, c):
    maxvs = [0] * (n + 1)
    minvs = [0] * (n + 1)
    for i in enumerate(c):
        for j in i[1]:
            maxvs[j] += s[i[0]]
            if k[i[0]] == 1:
                minvs[j] += s[i[0]]



    # maxmaxvs = max(maxvs)
    # print(maxvs)
    # print(minvs)
    # print(max(maxvs) - min(minvs[1:]) + 1)
    ans = -1
    for i in range(1,  n+1):
        ans = max(ans, maxvs[i]-min(minvs[1:i]+minvs[i+1:]))
    print(ans+1)





while True:
    N, M = map(int, input().split())
    if N == M == 0:
        break
    S = []
    K = []
    C = []
    for i in range(M):
        Skc = list(map(int, input().split()))
        S.append(Skc[0])
        K.append(Skc[1])
        C.append(Skc[2:])
    solve(N, M, S, K, C)

Submission status: Accepted

Solution code:
def main_a():
    y, m, d = map(int, input().split())
    a = (y - 1) // 3
    b = (y - 1) % 3
    c = a * 590 + 195 * b 
    if y % 3:
        a = (m - 1) // 2
        b = (m - 1) % 2
        c += a * 39 + b * 20
    else:
        c += (m - 1) * 20
    c += d - 1
    print(196470 - c)
def a():
    n = int(input())
    for i in range(n):
        main_a()

def main_b():
    s = input()
    ans = []
    for i in range(1,len(s)):
        ans.append(s[:i] + s[i:])
        ans.append(s[i-1::-1] + s[i:])
        ans.append(s[i-1::-1] + s[len(s):i-1:-1])
        ans.append(s[:i] + s[len(s):i - 1:-1])
        ans.append(s[i:] + s[:i])
        ans.append(s[i:] + s[i - 1::-1])
        ans.append(s[len(s):i - 1:-1] + s[i - 1::-1])
        ans.append(s[len(s):i - 1:-1] + s[:i])
    print(len(set(ans)))

def b():
    n = int(input())
    for i in range(n):
        main_b()

def main_c(n, m):
    a = [0] * n
    s = [0] * n
    for _ in range(m):
        skc = list(map(int, input().split()))
        si = skc[0]
        c = skc[2:]
        if skc[1] == 1:
            s[c[0] - 1] += si
        for i in c:
            a[i-1] += si
    an = max(a)
    anindex = a.index(an)

    sm = 10**20
    for i in range(n):
        if i != anindex:
            if sm > s[i]:
                sm = s[i]

    flg = False
 
    for i in range(n):
        if i != anindex:
            if s[i] == 0:
                flg = True
    if flg:
        ans = an + 1
    else:
        ans = an + 1 - sm
    print(ans)


def c():
    while 1:
        n, m = map(int, input().split())
        if n == m == 0:
            return
        main_c(n,m)

c()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#AOJ C

while 1:
    N,M = map(int,input().split())
    if N == 0 and M == 0:
        break
    I = [list(map(int,input().split())) for _ in range(M)]
    P = [0 for _ in range(N)]
    mP = [0 for _ in range(N)]
    for i in range(M):
        k = I[i][1]
        if k == 1:
            mP[I[i][2]-1] += I[i][0]
        for j in range(k):
            P[I[i][2+j]-1] += I[i][0]
    maxp = 0
    minp = float("inf")
    for i in range(N):
        if maxp < P[i]:
            maxp = P[i]
            index = i
    for i in range(N):
        if i != index:
            if minp > mP[i]:
                minp = mP[i]
    f = 0
    for i in range(N):
        if i != index:
            if mP[i] == 0:
                f = 1
    if f:
        print(max(P)+1)
    else:
        print(max(P)+1-minp)

Submission status: Accepted

Solution code:
import sys
def solve(n,m):
    d = [0]*n
    d_ = [0]*n
    for i in range(m):
        p = [int(x) for x in sys.stdin.readline().split()]
        for c in p[2:]:
            d[c-1] += p[0]
        if len(p) == 3:
            d_[p[2]-1] += p[0]
    ma = max(d)
    mi = min(d_)
    for i in range(n):
        if d[i] == ma:
            if d_[i] != mi:
                print(ma-mi+1)
                return
        else:
            if d_[i] == mi:
                print(ma-mi+1)
                return
    d.sort()
    d_.sort()
    print(max(d[-2]-mi,ma-d_[1])+1)
while 1:
    n,m = [int(x) for x in sys.stdin.readline().split()]
    if n == 0:
        break
    solve(n,m)

Submission status: Accepted

Solution code:
while True:
  N, M = map(int, input().split())
  if N==M==0:
    break
  Mi = [0] * N
  Ma = [0] * N
  for _ in range(M):
    L = list(map(int, input().split()))
    s, k = L[:2]
    if k==1:
      Mi[L[2]-1] += s
    for c in L[2:]:
      Ma[c-1] += s
  Mi_ = sorted(zip(Mi, range(N)))
  Ma_ = sorted(zip(Ma, range(N)))
  ans = Ma_[-1][0] - Mi_[0][0]
  #print(Ma, Mi)

  if Ma_[-1][1] == Mi_[0][1]:
    ans = max(Ma_[-1][0] - Mi_[1][0], Ma_[-2][0] - Mi_[0][0])
  print(ans + 1)

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n==m==0:break
    p_max=[0]*(n)
    p_min=[0]*(n)
    for i in range(m):
        quiz=list(map(int,input().split()))
        for j in quiz[2:]:
            p_max[j-1]+=quiz[0]
        if quiz[1]==1:
            p_min[j-1]+=quiz[0]
    pmax=max(p_max)
    while p_max.count(pmax)==1:
        k=p_max.index(pmax)
        del p_max[k]
        del p_min[k]
    print(pmax-min(p_min)+1)

Submission status: Accepted

Solution code:
while True:
  n, m = map(int, input().split())
  if n == 0:break
  max_score = [0] * n
  min_score = [0] * n
  for _ in range(m):
    line = list(map(int, input().split()))
    s, k = line[:2]
    for i in line[2:]:
      max_score[i - 1] += s
    if k == 1:
      min_score[line[2] - 1] += s
  
  print(max([max_score[i] - min(min_score[:i] + min_score[i + 1:]) + 1 for i in range(n)]))

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 = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-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 = []

    def f(n,m):
        xd = collections.defaultdict(int)
        nd = collections.defaultdict(int)
        for i in range(1,n+1):
            nd[i] = 0
            xd[i] = 0

        for _ in range(m):
            t = LI()
            s = t[0]
            if t[1] == 1:
                nd[t[2]] += s
            for i in t[2:]:
                xd[i] += s

        na = sorted(nd.items(), key=lambda x: [x[1], x[0]])
        xa = sorted(xd.items(), key=lambda x: [-x[1], x[0]])
        if na[0][0] != xa[0][0]:
            return xa[0][1] - na[0][1] + 1
        r = xa[1][1] - na[0][1] + 1
        t = xa[0][1] - na[1][1] + 1
        if r < t:
            r = t

        return r

    while 1:
        n,m = LI()
        if n == 0:
            break
        rr.append(f(n,m))

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


print(main())