Problem:


ポイントカード (Point Card)

問題

JOI 商店街ではポイントカードのサービスを行っている．各ポイントカードには 2N 個のマスがある．商品を購入すると，くじを引くことができ，結果によって「当たり」か「はずれ」の印がマスに押される．同じマスに印が 2 回押されることはない．2N 個のマスのうち N 個以上のマスに当たりの印が書かれたポイントカードは，景品と交換することができる．
また，ポイントカードの印は，1 マスにつき 1 円で書き換えてもらうことができる．

JOI 君は 2N 個のマスが全て埋まっているポイントカードを M 枚持っている．ポイントカード i (1 ≦ i ≦ M) には，Ai 個の当たり印と，Bi 個のはずれ印が押されている．JOI 君は M - 1 個以上の景品が欲しい．

JOI 君が M - 1 個以上の景品を得るために必要な費用の最小値を求めよ．

入力

入力は M + 1 行からなる．

1 行目には，2 個の整数 N, M (1 ≦ N ≦ 1000, 1 ≦ M ≦ 1000) が空白を区切りとして書かれている．これは，ポイントカードには 2N 個のマスがあり，JOI 君が M 枚のポイントカードを持っていることを表す．

続く M 行のうちの i 行目 (1 ≦ i ≦ M) には，それぞれ 2 個の整数 Ai, Bi (0 ≦ Ai ≦ 2N, 0 ≦ Bi ≦ 2N, Ai + Bi = 2N) が書かれており，ポイントカード i には Ai 個の当たり印と Bi 個のはずれ印が押されていることを表す．

 出力

JOI 君が M - 1 個以上の景品を得るために必要な費用の最小値を 1 行で出力せよ．

入出力例

入力例 1

4 5
1 7
6 2
3 5
4 4
0 8

出力例 1

4

入力例 2

5 4
5 5
8 2
3 7
8 2

出力例 2

0

入力例 1 においては，ポイントカード 1 のはずれ印を 3 つ当たり印に書き換えてもらい，ポイントカード 3 のはずれ印を 1 つ当たり印に書き換えてもらうと，4 円で 4 (= 5 - 1) 枚のカードが景品と交換可能になり，これが最小の費用である．

入力例 2 においては，既に 3 (= 4 - 1) 枚のカードが景品と交換可能なので，書き換えてもらう必要ない．

情報オリンピック日本委員会作 『第 16 回日本情報オリンピック JOI 2016/2017 予選競技課題』



Sample input:
4 5
1 7
6 2
3 5
4 4
0 8


Sample output:
4

Submission status: Wrong Answer

Solution code:
N , M = map(int , input().split(' '))
A, B = [], []
hit = 0
for i in range(M):
    tmp = input().split(' ')
    A.append(int(tmp[0]))
    B.append(int(tmp[1]))

hit_card = 0
for i in range(M):
    if A[i] >= N:
        hit_card += 1

sorted_A = sorted(A, reverse=True)
need_money = 0

if hit_card < (M - 1):
    need_hit = (M - 1) - hit_card

    for i in range(need_hit):
        need_money += N - sorted_A[i + need_hit]

print(need_money)

Submission status: Wrong Answer

Solution code:
N , M = map(int , input().split(' '))
A, B = [], []
hit = 0
tmp = 0
for i in range(M):
    tmp = input().split(' ')
    A.append(int(tmp[0]))
    B.append(int(tmp[1]))

hit_card = 0
for i in range(M):
    if A[i] >= N:
        hit_card += 1

sorted_A = sorted(A, reverse=True)
need_money = 0

if hit_card < (M - 1):
    need_hit = (M - 1) - hit_card

    for i in range(need_hit):
        need_money += N - sorted_A[i + need_hit]

print(need_money)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
cost = []
for _ in range(m):
  a, b = map(int, input().split())
  if a >= n:
    cost.append(0)
  else:
    cost.append(n - a)
print(sum(cost) - max(cost))

Submission status: Accepted

Solution code:
# coding: utf-8

N, M = list(map(int, input().split(' ')))
cards = [int(input().split(' ')[0]) for i in range(M)]
cards = sorted(cards)

cost = 0
for i in range(1, M):
    if cards[i] >= N: break
    cost += N - cards[i]

print(cost)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=x=0
for i in range(m):
    a,b=map(int,input().split())
    if n-a>0:s+=n-a
    if n-a>x:x=n-a
print(s-x)

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
a = []
cnt = 0
for _ in range(m):
  c, d = map(int, raw_input().split())

  if c >= n:
    cnt += 1
  else:
    a.append(c)

a.sort(reverse=True)

ans = 0
for i in range(m-1-cnt):
  ans += n-a[i]

print ans

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
cards = [list(map(int, input().split())) for _ in range(M)]
hit=ans=0
for n, m in sorted(cards, key=lambda x: x[0])[::-1]:
    if n >= N:
        hit += 1
    else:
        ans += N-n
        hit += 1
    if hit == M-1:
        break
print(ans)

Submission status: Accepted

Solution code:
import sys

def main():
    N,M = map(int,input().split())
    arr = []
    for i in range(M):
        x,y = map(int,input().split())
        arr.append(x)
    arr = sorted(arr,reverse=True)
    ans = 0
    cnt = 0
    for x in arr:
        if cnt >= M-1:
            break
        cnt += 1
        if x < N:
            ans += N - x
    print(ans)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=[list(map(int,input().split()))for i in range(m)]
c=[]
for i in p:
	a,b=i
	if a>=n:o=0
	else:o=n-a
	c.append(o)
c.sort()
c.pop()
print(sum(c))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=[list(map(int,input().split()))for i in range(m)]
c=[n-a if n>a else 0for a,b in p]
print(sum(c)-max(c))

Submission status: Accepted

Solution code:
n,m=[int(s)for s in input().split(" ")]
a=[int(input().split(" ")[0])for i in range(m)]
a.sort()
if a[1]>=n:print(0)
else:
    cost=0
    ac=a[1:]
    for i in ac:
        if i<n:cost+=n-i
        else:
            print(cost)
            break

Submission status: Accepted

Solution code:
N , M = map(int , input().split(' '))
A, B = [], []
hit = 0
for i in range(M):
    tmp = input().split(' ')
    A.append(int(tmp[0]))
    B.append(int(tmp[1]))

hit_card = 0
for i in range(M):
    if A[i] >= N:
        hit_card += 1

sorted_A = sorted(A, reverse=True)
need_money = 0

if hit_card < (M - 1):
    need_hit = (M - 1) - hit_card

    for i in range(need_hit):
        need_money += N - sorted_A[i + hit_card]

print(need_money)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
C = [next(map(int, input().split())) for i in range(M)]
C.sort(reverse = True)
ans = 0
for i in range(M-1):
    ans += max(0, N - C[i])
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
count = [0 for _ in range(m)]
for i in range(m):
    b = list(map(int, input().split()))[1]
    count[i] = max(0, b - n)
print(sum(count) - max(count))

Submission status: Accepted

Solution code:
# AOJ 0631: Point Card
# Python3 2018.7.2 bal4u

n, m = map(int, input().split())
ans, mi = 0, n*2
for i in range(m):
	a, b = map(int, input().split())
	if a < n:
		ans += n-a
		mi = min(mi, a)
print(ans if ans <= 0 else ans-(n-mi));

Submission status: Accepted

Solution code:
N,M = map(int,input().split())

keihin = M-1

cards = []

for _ in range(M):
    cards.append(list(map(int,input().split())))
    
ans = 0

sorted_cards = sorted(cards, key=lambda x:x[0],reverse=True)

cnt = 0

while cnt < keihin:
    if sorted_cards[cnt][0] >= N:
        cnt+=1
    else:
        ans += (N-sorted_cards[cnt][0])
        cnt+=1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())

a = [0 for i in range(m)]
b = [0 for i in range(m)]


for i in range(m):
    a[i],b[i] = map(int,input().split())

a.sort()
c = 0

for i in range(m-1):
    if n <= a[i+1]:
        break
    else:
        c += n-a[i+1]

print(c)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
count=0
s=[]
for i in range(m):
    a,b=map(int,input().split())
    if n>a:
        count+=1
        s.append(n-a)
if count<m-1:
    z=max(s)
    s.remove(z)
    print(sum(s))
else:
    print("0")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = []
for _ in range(M):
	n, m = map(int, input().split())
	a.append(n)
a.sort(reverse=True)
result = 0
for i in range(M-1):
	if a[i]<N: result += N-a[i]

print(result)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB=list()
for i in range(M):
  AB.append(list(map(int,input().split())))
C=0
AB.sort(reverse=True)
for i in range(M-1):
  C=C+max(0,N-AB[i][0])
print(C)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [int(input().split()[0]) for i in range(M)]

mi = min(A)
del A[A.index(mi)]

ans = 0
for v in A:
	ans += max(0, N - v)
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x = []
money = 0
for i in range(m):
    a,b = map(int,input().split())
    if a < n:
        x += [a]

x.sort()

if len(x) > 1:
    for j in reversed(range(1,len(x))):
        money += n - x[j]

print(money)

Submission status: Accepted

Solution code:
N,M=[int(i) for i in input().split(" ")]

cards=[]
for i in range(M):
    A,B=[int(j) for j in input().split(" ")]
    cards.append((A,B))

cards=sorted(cards)
retval=0
for c in cards[1::]:
    if c[0]<N:
        retval+=N-c[0]
print(retval)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
cards = [list(map(int, input().split())) for _ in range(m)]
cards = sorted(cards, key=lambda x: x[0])[::-1]
cost = 0
for card in cards[:-1]:
    if card[0] < n:
        cost += n - card[0]

print(cost)

Submission status: Accepted

Solution code:
#B
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(M)]

AB.sort(reverse=True)
ans = 0
for i in range(M-1):
    ans+=max(0,N-AB[i][0])

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
numbers = []
money = 0
for i in range(M):
    a,b = map(int,input().split())
    numbers.append(a)
numbers.sort(reverse = True)
for j in range(M-1):
    if numbers[j] < N:
        money += N-numbers[j]
print(money)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = []
for i in range(m):
    a.append(int(input().split()[0]))
a.sort()
count = 0
for i in range(1, m):
    if a[i] < n:
        count += (n-a[i])
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Point Card
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0631

"""
import sys


def solve(cards, n, m):
    ans = 0
    for _ in range(1, m):
        atari, _ = cards.pop()
        ans += max(0, n - atari)
    return ans


def main(args):
    n, m = map(int, input().split())
    cards = sorted([[int(i) for i in input().split()] for _ in range(m)])
    ans = solve(cards, n, m)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
less=[]
cnt=0
expense=0
for i in range(m):
    if ab[i][0]>=n:
        cnt+=1
    else:
        less.append(ab[i][1]-n)
if cnt<m-1:
    less.sort()
    expense=sum(less[:m-1-cnt])
print(expense)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A_list = []
for i in range(M):
    A, B = map(int, input().split())
    if B > N:
          A_list.append(A)
list_num = len(A_list)
if list_num <= 1:
    print(0)
else:
    sort_list = sorted(A_list, reverse=True)
    add_list = sort_list[0:(list_num-1)]
    print_num = (list_num - 1) * N - sum(add_list)
    print(print_num)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=[]
for i in range(m):
    p.append(list(map(int,input().split())))
p.sort()
p.pop(0)
ans=0
for i in p:
    if i[0]<n:ans+=i[1]-n
    else:break
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
lst = [list(map(int,input().split()))[0] for i in range(m)]
lst.sort()
ans=0
i=1
while lst[i] < n :
    ans+=n-lst[i]
    i+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

point = []
for _ in range(m):
    atari, hazure = map(int, input().split())
    point.append([atari, hazure])

point.sort(reverse=True)

ans = 0
for [atari, _] in point[:m-1]:
    if atari >= n:
        continue
    else:
        ans += n - atari

print(ans)

Submission status: Accepted

Solution code:
l=[]
n,m=map(int,input().split())
for i in range(m):
  a,b=map(int,input().split())
  k=0
  if(a<n):
    k=n-a
  l.append(k)
l.sort()
ans=0
for i in range(0,m-1):
  ans+=l[i]
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))
    
ab = sorted(ab,key = lambda x:x[1])
del ab[-1]
cnt = 0
for asd in ab:
    if (asd[0]<n):
        cnt += (n-asd[0])
print(cnt)