Problem:


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

JAG 模擬予選練習会

ACM-ICPC OB/OGの会 (Japanese Alumni Group; JAG) には模擬コンテストで出題する問題のストックが N 問あり，それぞれの問題は 1 から N の整数で番号付けられている．
それぞれの問題について難易度評価と推薦投票が行われており，問題 i の難易度は di で，推薦度は vi である．
また，難易度の最大値は M である．

次のコンテストでは，難易度 1 から M の問題をそれぞれ 1 問ずつ，計 M 問出題する予定である．
コンテストのクオリティを上げるために推薦度の合計が最大になるように問題を選定したい．
ただし，JAG の作問力はすさまじいので，各難易度の問題が最低でも 1 問以上ずつあると仮定してよい．

あなたの仕事は，条件を満たすように問題を選定したときの推薦度の和の最大値を求めるプログラムを作成することである．

Input

入力は複数のデータセットからなる．
各データセットは次の形式で表される．

N M
d1 v1
...
dN vN

データセットの 1 行目には，問題ストックの数を表す整数 N と，難易度の最大値 M が空白区切りで与えられる．
これらの数は 1 ≤ M ≤ N ≤ 100 を満たす．
続く N 行の内 i 行目には，問題 i の難易度と推薦度を表す整数 di と vi が空白区切りで与えられる．
これらの数は 1 ≤ di ≤ M および 0 ≤ vi ≤ 100 を満たす．
また，各 1 ≤ j ≤ M について，di = j となる i が 1 つ以上存在することが保証される．

入力の終わりは空白で区切られた 2 つのゼロで表される．
また，データセットの数は 50 を超えない．

Output

各データセットについて，各難易度から 1 問ずつ出題するときの，出題する問題の推薦度の和の最大値を 1 行に出力せよ．

Sample Input

5 3
1 1
2 3
3 2
3 5
2 1
4 2
1 7
2 1
1 3
1 5
6 1
1 3
1 2
1 8
1 2
1 7
1 6
20 9
4 10
2 4
5 3
6 6
6 3
7 4
8 10
4 6
7 5
1 8
5 7
1 5
6 6
9 9
5 8
6 7
1 4
6 4
7 10
3 5
19 6
4 1
6 5
5 10
1 10
3 10
4 6
2 3
5 4
2 10
1 8
3 4
3 1
5 4
1 10
1 3
5 6
5 2
1 10
2 3
0 0

サンプルのデータセットは5つあり，順に

1行目から6行目までが1つ目 (N = 5, M = 3) のテストケース，

7行目から11行目までが2つ目 (N = 4, M = 2) のテストケース，

12行目から18行目までが3つ目 (N = 6, M = 1) のテストケース，

19行目から39行目までが4つ目 (N = 20, M = 9) のテストケース，

40行目から59行目までが5つ目 (N = 19, M = 6) のテストケースをそれぞれ表す．

Output for Sample Input

9
8
8
71
51



Sample input:
5 3
1 1
2 3
3 2
3 5
2 1
4 2
1 7
2 1
1 3
1 5
6 1
1 3
1 2
1 8
1 2
1 7
1 6
20 9
4 10
2 4
5 3
6 6
6 3
7 4
8 10
4 6
7 5
1 8
5 7
1 5
6 6
9 9
5 8
6 7
1 4
6 4
7 10
3 5
19 6
4 1
6 5
5 10
1 10
3 10
4 6
2 3
5 4
2 10
1 8
3 4
3 1
5 4
1 10
1 3
5 6
5 2
1 10
2 3
0 0


Sample output:
9
8
8
71
51

Submission status: Accepted

Solution code:
# AOJ 2823: JAG Practice Contest
# Python3 2018.7.11 bal4u

while True:
	N, M = map(int, input().split())
	if N == 0: break
	ma = [0]*(M+1)
	for i in range(N):
		d, v = map(int, input().split())
		ma[d] = max(ma[d], v)
	print(sum(ma))

Submission status: Accepted

Solution code:
#d = むずかしさ, v = 推薦度
ans2 = []
while(1):
    tip = []
    tmp = []
    ans = 0
    n, m = map(int,input().split())
    if n == 0 and m == 0:
        break
    else:
        for i in range(n):
            d, v = map(int,input().split())
            tip.append([d, v])
        tip = sorted(tip, key = lambda x: x[1])
        tip.reverse()
        #print(tip)
        for i in range(n):
            if tip[i][0] in tmp:
                pass
            else:
                ans += tip[i][1]
                m += 1
                tmp.append(tip[i][0])
        #print("ans = {}".format(ans))
        ans2.append(ans)

for i in ans2:
    print(i)

Submission status: Accepted

Solution code:
while True:
    N,M=map(int,input().split())
    if N == 0 and M == 0:
        break
    mp = {}
    for _ in [0]*N:
        d,v=map(int,input().split())
        if d in mp:
            mp[d] = max(mp[d],v)
        else :
            mp[d] = v
            maxi=0
    for v in mp.values():
                maxi+=v
    print(maxi)

Submission status: Accepted

Solution code:
while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    p = [0]*m
    for i in xrange(n):
        d, v = map(int, raw_input().split())
        p[d-1] = max(p[d-1], v)
    print sum(p)

Submission status: Accepted

Solution code:
import bisect
while True:
    n, m = map(int, input().split())
    if n == 0:break
    a = [tuple(map(int, input().split())) for _ in range(n)]
    a.sort(key = lambda x:x[1], reverse = True)
    a.sort(key = lambda x:x[0])
    v = 0
    for i in range(1, m + 1):v += a[bisect.bisect_left(a,(i,0))][1]
    print(v)

Submission status: Accepted

Solution code:
while True:
    (n, m) = tuple(map(int, input().split()))
    if n == 0:
        break
    arr = [0 for i in range(m + 1)]
    for i in range(n):
        inp = list(map(int, input().split()))
        arr[inp[0]] = max(inp[1], arr[inp[0]])
    res = 0
    for e in arr:
        res += e
    print(res)

Submission status: Accepted

Solution code:
while True:
    N,M=map(int,input().split())
    if N==0 and M==0:
        break
    l = [0]*M
    for i in range(N):
        d,v=map(int,input().split())
        if l[d-1]<v:
            l[d-1]=v
    total = 0
    for i in range(M):
        total += l[i]

    print(total)

Submission status: Accepted

Solution code:
#21:40
#21:
while True:
    n,m = map(int,input().split())
    if n ==0 : break


    #難易度と最大推薦度の辞書
    question_dict={}

    for i in range(n):
        difficult,recommend = map(int,input().split())
        if difficult in question_dict:
            question_dict[difficult] = max(question_dict[difficult],recommend)
        else:
            question_dict[difficult] = recommend

    print(sum(question_dict.values()))

Submission status: Accepted

Solution code:
while 1:
    n, m = map(int, input().split())
    if n == 0:
        break
    s = [0]*(m+1)
    for _ in range(n):
        d, v = map(int, input().split())
        if s[d] < v:
            s[d] = v
    print(sum(s))

Submission status: Accepted

Solution code:
while True:
  n,m=map(int,input().split())
  if n==0:exit()
  a=[0]*(m+1)
  for _ in range(n):
    d,v=map(int,input().split())
    a[d]=max(a[d],v)
  print(sum(a))

Submission status: Accepted

Solution code:
while True:
    line = input()

    if line == "0 0":
        break

    stock, max_difficulty = map(int, line.split(" "))

    max_recommend_list = [0 for _ in range(max_difficulty)]

    for i in range(stock):
        difficulty, recommend = map(int, input().split(" "))
        max_recommend_list[difficulty - 1] = max(max_recommend_list[difficulty - 1], recommend)

    print(sum(max_recommend_list))

Submission status: Accepted

Solution code:
while True:
	n,m = map(int,input().split())
	if n+m == 0:break
	lst = []
	for _ in range(n):
		d,v = map(int,input().split())
		lst.append((d,v))
	lst.sort()
	ans = 0
	for i,a in enumerate(lst):
		if i == len(lst)-1:
			ans += a[1]
			continue
		if lst[i+1][0] != a[0]:
			ans += a[1]
	print(ans)

Submission status: Accepted

Solution code:
import sys

def solve(n, m):
    l = []
    for i in range(n):
        d, v = map(int, input().split())
        l.append((d, v))

    l.sort(reverse=True)

    now = -1
    count = 0
    for i in l:
        if now == i[0]:
            continue
        else:
            count += i[1]
            now = i[0]

    print(count)


while True:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    solve(n, m)

Submission status: Accepted

Solution code:
"JAG模擬予選練習会"
while True:
    N, M = map(int, input().split())  # 問題の数N, 難易度の幅M
    if N == 0 and M == 0:
        break

    max_value = {}
    for i in range(1, M+1):
        max_value[i] = 0

    for i in range(N):
        d, v = map(int, input().split())
        max_value[d] = max(max_value[d], v)

    ans = sum(max_value.values())
    print(ans)

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n==m==0:break
    s=set()
    c=0
    for d,v in sorted([list(map(int,input().split()))for i in range(n)],key=lambda x:-x[1]):
        if d in s:continue
        c+=v
        s.add(d)
        if len(s)>=m:
            break
    print(c)

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, input().split())
    if not n and not m:
        break

    dataset = [0 for _ in range(m)]
    for i in range(n):
        d, v = map(int, input().split())
        dataset[d - 1] = max(v, dataset[d - 1])
    print(sum(dataset))

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n==m==0:break
    cont=[0]*(m+1)
    for i in range(n):
        d,v=map(int,input().split())
        if cont[d]<v:cont[d]=v
    print(sum(cont))

Submission status: Accepted

Solution code:
from collections import defaultdict
while True:
  n, m = map(int, input().split())
  if n == 0:break
  dic = defaultdict(int)
  for _ in range(n):
    d, v = map(int, input().split())
    dic[d] = max(dic[d], v)
  print(sum(dic.values()))

Submission status: Accepted

Solution code:
while 1:
    n, m = map(int, input().split())
    if n == 0:
        break

    rec = [0] * (m+1)
    for _ in range(n):
        d, v = map(int, input().split())
        if rec[d] < v:
            rec[d] = v

    print(sum(rec))

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**13
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):
        a = [LI() for _ in range(n)]
        t = collections.defaultdict(int)
        for d,v in a:
            if t[d] < v:
                t[d] = v
        r = 0
        for i in range(1, m+1):
            r += t[i]
        return r

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

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


print(main())

Submission status: Accepted

Solution code:
while True:

    N,M = map(int,input().split())

    if N == 0 and M == 0:
        break
    
    ans = 0
    
    di = []
    vi = []

    for i in range(0,N):
        d,v = map(int,input().split())
        di.append(d)
        vi.append(v)
        
    for i in range(1,M+1):
        max = 0
        for j in range(0,N):
            if di[j] == i and max < vi[j]:
                max = vi[j]
        ans+=max

    print(ans)

Submission status: Runtime Error

Solution code:
m,n=map(int,input().split())
a =[]
for _ in range(m):
    a.append(list(map(int,input().split())))
for index in range(m):
    a[index].append(sum(a[index]))
for a_column in a:
    for num in a_column[:-1]:
        print(num, end=' ')
    print(a_column[-1])
for row_index in range(n+1):
    sum = 0
    for a_column in a:
        sum += a_column[row_index]
    print(sum, end=' ')
print()