Problem:


Score : 700 points

Problem Statement

In the final of CODE FESTIVAL in some year, there are N participants.
The height and power of Participant i is H_i and P_i, respectively.

Ringo is hosting a game of stacking zabuton (cushions).

The participants will line up in a row in some order, and they will in turn try to add zabuton to the stack of zabuton.
Initially, the stack is empty.
When it is Participant i's turn, if there are H_i or less zabuton already stacked, he/she will add exactly P_i zabuton to the stack. Otherwise, he/she will give up and do nothing.

Ringo wants to maximize the number of participants who can add zabuton to the stack.
How many participants can add zabuton to the stack in the optimal order of participants?

Constraints

1 \leq N \leq 5000

0 \leq H_i \leq 10^9

1 \leq P_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
H_1 P_1
H_2 P_2
:
H_N P_N

Output

Print the maximum number of participants who can add zabuton to the stack.

Sample Input 1

3
0 2
1 3
3 4

Sample Output 1

2

When the participants line up in the same order as the input, Participants 1 and 3 will be able to add zabuton.

On the other hand, there is no order such that all three participants can add zabuton. Thus, the answer is 2.

Sample Input 2

3
2 4
3 1
4 1

Sample Output 2

3

When the participants line up in the order 2, 3, 1, all of them will be able to add zabuton.

Sample Input 3

10
1 3
8 4
8 3
9 1
6 4
2 3
4 2
9 2
8 3
0 1

Sample Output 3

5



Sample input:
3
0 2
1 3
3 4


Sample output:
2

Submission status: Memory Limit Exceeded

Solution code:
N = int(input())
"""
dp[i][j] -> i番目の人間までみる。j人が積むときの最小値。

"""
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x:x[0]+x[1])
dp = [[float("INF")]*(N+1) for _ in range(N+1)]
for i in range(N):
    dp[i][0] = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        if dp[i-1][j-1] <= HP[i-1][0]:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+HP[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]
for j in range(N,-1,-1):
    if dp[-1][j] != float("INF"):
        print(j)
        break

Submission status: Memory Limit Exceeded

Solution code:
N = int(input())
men = []
for i in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])
dp = [[float("INF")]*(N+1) for _ in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    H,P=men[i-1][0],men[i-1][1]
    for j in range(i+1):
        if j == 0:
            dp[i][j] = 0
        else:
            if dp[i-1][j-1]<=H:
                dp[i][j] = min(dp[i-1][j-1]+P,dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j] != float("INF"):
        print(j)
        break

Submission status: Accepted

Solution code:
"""
余裕の小さい人から先に座布団を積ませた方がよい。
余裕の大きさは自分の身長と他人のパワーで決まる。
いまここにAとBがいる。
このとき、Bp > AhならAが先に積んだ方がよい。
Ap > Bh ならBが先に積んだ方がよい。
これは書き換えるとAh - Bp < 0ならAがさき、Bh - Ap < 0ならBが先。
Ah - Bp < Bh - ApならAが先、Ah - Bp > Bh - ApならBが先である。
書き換えると、
Ah + Ap < Bh + Bp ならAが先、Ah + Ap > Bh + Bp ならBが先である。
したがって身長+パワーで昇順に並び替えればよい。
"""
N = int(input())
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key= lambda x:x[0]+x[1])
dp = [float("INF")]*(N+1)
dp[0] = 0
for i in range(N):
    h,p = HP[i]
    for j in range(N,0,-1):
        if dp[j-1] <= h:
            dp[j] = min(dp[j],dp[j-1]+p)

for j in range(N,-1,-1):
    if dp[j] != float("INF"):
        print(j)
        break

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
hp = [tuple(map(int, input().split())) for _ in range(n)]
hp.sort(key=lambda x: x[0]+x[1])
dp = [10**15] * (n+1)
dp[0] = 0
for i in range(n):
    h,p = hp[i]
    for j in range(n,0,-1):
        if dp[j-1]<=h:
            dp[j] = min(dp[j], dp[j-1]+p)
#     print(dp)
for i in range(n, -1, -1):
    if dp[i]<10**15:
        break
ans = i
print(ans)

Submission status: Accepted

Solution code:
"""
Aさん：身長Ha , パワーPa
Bさん：身長Hb , パワーPb
二人どちらも積めるのに順番を間違えたばかりに一人しか積めない、という事態を避けたい。
Aさんが先に積むべき？Bさんが先に積むべき？
Aさん、Bさんの手前までの時点で高さSまで積みあがっているとする。S <= min(Hb,Ha)とする。

S+Pa > Hb　かつ S+Pb <= HaならBが先
S+Pb > Ha　かつ S+Pa <= HbならAが先

Pa-Hb > Pb-Ha ならBが先でAが後
書き換えるとPa+Ha > Pb+HbならBが先でAが後
つまり、P+H順にソートしてナップサックすればよい
"""


N = int(input())
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key = lambda x:x[0]+x[1])
#dp[i][j] -> j人積む場合の座布団の最小枚数
dp = [float("INF")]*(N+1)
dp[0] = 0
for h,p in HP:
    for j in range(N,0,-1):
        if dp[j-1] <= h:
            dp[j] = min(dp[j],dp[j-1]+p)

for j in range(N,-1,-1):
    if dp[j] != float("INF"):
        print(j)
        break

Submission status: Accepted

Solution code:
N = int(input())
"""
dp[i][j] -> i番目の人間までみる。j人が積むときの最小値。

"""
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x:x[0]+x[1])
dp = [float("INF")]*(N+1)
dp[0] = 0
for i in range(1,N+1):
    for j in range(N,0,-1):
        if dp[j-1] <= HP[i-1][0]:
            dp[j] = min(dp[j],dp[j-1]+HP[i-1][1])
for j in range(N,-1,-1):
    if dp[j] != float("INF"):
        print(j)
        break

Submission status: Accepted

Solution code:
import bisect

N=int(input())
hito=[]
for i in range(N):
    h,p=map(int,input().split())
    hito.append((h+p,h,p))

hito.sort()
data=[0]
for i in range(0,N):
    gomi,h,p=hito[i]
    for j in range(len(data)-1,-1,-1):
        if j==len(data)-1:
            if h>=data[-1]:
                data.append(data[-1]+p)
            if h>=data[j-1] and j!=0:
                data[j]=min(data[j],data[j-1]+p)
        else:
            if h>=data[j-1] and j!=0:
                data[j]=min(data[j],data[j-1]+p)
    

print(len(data)-1)

Submission status: Accepted

Solution code:
N = int(input())
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x: x[0]+x[1])
ceil = max(HP,key=lambda x: x[0])[0]
#dp[i][j] -> i人目まで見る。j人積むときの、座布団の枚数の最小値
dp = [[ceil+1]*(N+1) for _ in range(N+1)]
ans = 0
for i in range(N+1):
    dp[i][0] = 0
for i in range(1,N+1):
    h,p = HP[i-1]
    for j in range(1,N+1):
        if dp[i-1][j-1]<=h:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
            ans = max(ans,j)
        else:
            dp[i][j] = dp[i-1][j]

print(ans)

Submission status: Accepted

Solution code:

"""
https://atcoder.jp/contests/cf17-final/tasks/cf17_final_d

全て置けるかの判定を考える
H+Pで昇順ソート
後ろから見ていって、その時点での座布団がH+P以下なら○　だめならX
を付けてPを引く
を繰り返し、全て○なら全員置ける(丸の数以上の答えであることが確定する)

あとは前から見ていってdp?
dp[i][j] = i人目まで見てj人置いた時の最小の枚数
→H+Pでソートするのが正しいなら絶対おｋなんだが…

"""

N = int(input())

SHP = []

for i in range(N):

    h,p = map(int,input().split())
    SHP.append( (h+p,h,p) )

SHP.sort()

dp = [float("inf")] * (N+1)
dp[0] = 0

for i in range(N):

    s,h,p = SHP[i]

    for j in range(N-1,-1,-1):

        if dp[j] <= h:
            dp[j+1] = min(dp[j+1] , dp[j] + p)

ans = 0
for i in range(N+1):
    if dp[i] != float("inf"):
        ans = i
print (ans)

Submission status: Accepted

Solution code:
n = int(input())
hp = [list(map(int,input().split())) for i in range(n)]
hp.sort(key = lambda x:x[0]+x[1])
dp = [[10**18 for i in range(j+1)] for j in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
  h,p = hp[i-1]
  for j in range(i+1):
    if j < i:
      dp[i][j] = dp[i-1][j]
    if j and dp[i-1][j-1] <= h:
      dp[i][j] = min(dp[i][j],dp[i-1][j-1]+p)
for i in range(n+1):
  if dp[-1][i] == 10**18:
    print(i-1)
    break
else:
  print(n)

Submission status: Accepted

Solution code:
N = int(input())
men = []
for _ in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])

maxH = max(men)[0]
inf = maxH+1
#dp[i][j] -> i人目までみたとき、j人が座布団を積む場合の最小枚数
dp = [[-1]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    h,p,a = men[i-1]
    for j in range(1,N+1):
        if 0 <= dp[i-1][j-1] <= h:
            if dp[i-1][j] == -1:
                dp[i][j] = dp[i-1][j-1]+p
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
        else:
            dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j] != -1:
        print(j)
        break

Submission status: Accepted

Solution code:
N = int(input())
HP = [tuple(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x: sum(x))

INF = float('inf')
dp = [0]
maxj = 0
for i,(h,p) in enumerate(HP):
	dp2 = [INF] * (maxj + 2)
	for j in range(maxj,-1,-1):
		dp2[j] = min(dp2[j], dp[j])
		if dp[j] <= h:
			dp2[j+1] = min(dp2[j+1], dp[j] + p)
			if j == maxj:
				maxj += 1
	dp = dp2
print(maxj)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
n = int(input())
men = [tuple(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: (x[0]+x[1], -x[0]))
allowed = [-1 for _ in range(n)]
allowed[n-1] = men[-1][0]
for i in range(n-2, -1, -1):
	allowed[i] = max(allowed[i+1], men[i][0])

INF = 10**10
dp = [INF for _ in range(n+1)]
dp[0] = 0
for i in range(n):
	for j in range(i+1, 0, -1):
		if dp[j-1] <= men[i][0]:
			dp[j] = min(dp[j], dp[j-1] + men[i][1])

#print(dp)
for i in range(n+1):
	if dp[i] < INF:
		ans = i
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

    N = int(input())
    HP = []
    for i in range(N):
        h, p = map(int, input().split())
        HP.append((h, p, h+p))
    HP.sort(key=itemgetter(2))

    inf = 10**15
    dp = [[inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        h, p, _ = HP[i]
        for j in range(N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j+1 <= N:
                if h >= dp[i][j]:
                    dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + p)
    for i in range(N, -1, -1):
        if dp[-1][i] < inf:
            print(i)
            break


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
M = []
for _ in range(N):
    h, p = map(int, input().split())
    M.append((h, p))
M = sorted(M, key=lambda x: x[0] + x[1])
dp = [10 ** 9 + 1] * (N+1)
dp[0] = 0
ans = 0
for h, p in M:
    for i in range(N-1, -1, -1):
        if dp[i] <= h:
            dp[i+1] = min(dp[i+1], dp[i] + p)
            ans = max(ans, i+1)

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:sum(x))
    dp=[10**10]*(n+1)
    dp[0]=0
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**10:
            print(i)
            break
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N = int(input())
H,P = np.array([[int(x) for x in input().split()] for _ in range(N)],dtype=np.int64).T

i = (H+P).argsort()
H = H[i]; P = P[i]

# 人数 -> 最小高さ
INF = 10**18
dp = np.full(N+1,INF,dtype=np.int64)
dp[0] = 0
for h,p in zip(H,P):
    prev = dp
    dp = prev.copy()
    can_add = (prev[:-1] <= h)
    np.minimum(dp[1:], np.where(can_add, prev[:-1]+p, INF), out=dp[1:])

answer = np.where(dp < INF)[0][-1]
print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

INF = 10 ** 18

N = input()

ls = []
for i in range(N):
    H, P = map(int, raw_input().split())
    ls.append((H + P, H, P))

ls.sort()

DP = [INF] * (N + 1)
DP[0] = 0

for i in range(N):
    _, H, P = ls[i]
    for j in range(i, -1, -1):
        if DP[j] <= H and DP[j + 1] > DP[j] + P:
            DP[j + 1] = DP[j] + P

ans = 0
for i in range(N + 1):
    if DP[i] < INF:
        ans = i

print ans

Submission status: Accepted

Solution code:
from bisect import*
N = int(input())
P = []

for i in range(N):
    h, p = map(int, input().split())
    P.append((h+p, h, p))
P.sort()

dp = [10**18]*(N+1)
dp[0] = 0
for i in range(N):
    k, h, p = P[i]
    idx = bisect(dp, h)
    for j in range(idx-1, -1, -1):
        dp[j+1] = min(dp[j]+p, dp[j+1])
    #print(idx)
    #print(dp[:idx+1])
print(bisect(dp, 10**17)-1)

Submission status: Runtime Error

Solution code:
N = int(input())
"""
dp[i][j] -> i番目の人間までみる。j人が積むときの最小値。

"""
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x:x[0]+x[1])
dp = [[float("INF")]*(N+1) for _ in range(N)]
for i in range(N):
    dp[i][0] = 0
dp[0][1] = HP[1][1]
for i in range(1,N):
    for j in range(1,N+1):
        if dp[i-1][j-1] <= HP[i][0]:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+HP[i][1])
        else:
            dp[i][j] = dp[i-1][j]
for j in range(N,-1,-1):
    if dp[-1][j] != float("INF"):
        print(j)
        break

Submission status: Runtime Error

Solution code:
N = int(input())
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x: x[0]+x[1])
ceil = max(HP,key=lambda x: x[0])[0]
#dp[i][j] -> i人目まで見る。j人積むときの、座布団の枚数の最小値
dp = [ceil+1]*(N+1)
ans = 0
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    h,p = HP[i]
    for j in range(N,0,-1):
        if dp[j-1]<=h:
            dp[j] = min(dp[j],dp[j-1]+p)
            ans = max(ans,j)

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
men = []
for _ in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])

inf = max(H)+1
dp = [[inf]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    h,p,a = men[i-1]
    for j in range(1,N+1):
        if dp[i-1][j-1] <= h:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
        else:
            dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j] != inf:
        print(j)
        break

Submission status: Runtime Error

Solution code:
def main():
    import sys
     input=sys.stdin.readline
    n = int(input())
    hp = sorted([tuple(map(int, input().split()))
                 for _ in [0]*n], key=lambda x: sum(x))
    dp = [10**10]*(n+1)
    dp[0] = 0
    for c, (h, p) in enumerate(hp):
        for k in range(c, -1, -1):
            if dp[k] <= h:
                dp[k+1] = min(dp[k+1], dp[k]+p)
    for i in range(n, -1, -1):
        if dp[i] != 10**10:
            print(i)
            break


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
men = [list(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: x[0]+x[1], x[0])
dp = [[0, 0] for _ in range(n+1)]
for i in range(1, n+1):
	for j in range(i):
		if dp[j][0] <= men[i-1][0]:
			if dp[j][1]+1 == dp[i][1]:
				dp[i][0] = min(dp[i][0], dp[j][0] + men[i-1][1])
			elif dp[j][1]+1 > dp[i][1]:
				dp[i][1] = dp[j][1]+1
				dp[i][0] = dp[j][0] + men[i-1][1]
ans = 0
for i in range(1, n+1):
	ans = max(ans, dp[i][1])
print(ans)

Submission status: Runtime Error

Solution code:
from functools import cmp_to_key

class Boxes:

    def __init__(self,str,weight):
        self.str=str
        self.weight=weight
    
    def __repr__(self):
        return '({} , {})'.format(self.str,self.weight)

def box_cmp(box_a,box_b):

    if(box_a.str+box_a.weight > box_b.str+box_b.weight):
        return -1
    elif(box_a.str+box_a.weight < box_b.str+box_b.weight):
        return 1
    else:
        return 0

def get_max_seq(index,weight_sum,count):
    res=-1
    if(index<0):
        return count
    
    if(boxes[index].str>=weight_sum):
        res=get_max_seq(index-1,weight_sum+boxes[index].weight,count+1)

    res=max(res,get_max_seq(index-1,weight_sum,count))
    return res

def dyna(boxes,N):
    print('boxes: ',boxes)
    INF=int(1e10+7)
    dp=[INF]*(N+1)
    dp[0]=0
    # print('dp: ',dp)

    for  i in range(0,N):
        for j in range(i,-1,-1):

            if(dp[j]<=boxes[i].str):
                dp[j+1]=min(dp[j+1],dp[j] + boxes[i].weight)

    # print('dp: ',dp)

    for i in range(N,-1,-1):
        if(dp[i]!=INF):
            return i
    

# b_o=[(1,3),(3,4),(2,3),(5,6),(3,5),(8,7),(4,6)]
#boxes= [ Boxes(x[0],x[1]) for x in b_o]

boxes = []
N=int(input())
for _ in range(N):
    a=[ int(x) for x in input().split()]
    boxes.append(Boxes(a[0],a[1]))


# print('input len: ',len(boxes))
# print(boxes)
boxes.sort(key=cmp_to_key(box_cmp),reverse=True)
# print(boxes)
#print(get_max_seq(N-1,0,0))
 print(dyna(boxes,N))

Submission status: Runtime Error

Solution code:
from functools import cmp_to_key

class Boxes:

    def __init__(self,str,weight):
        self.str=str
        self.weight=weight
    
    def __repr__(self):
        return '({} , {})'.format(self.str,self.weight)

def box_cmp(box_a,box_b):

    if(box_a.str+box_a.weight > box_b.str+box_b.weight):
        return -1
    elif(box_a.str+box_a.weight < box_b.str+box_b.weight):
        return 1
    else:
        return 0

def get_max_seq(index,weight_sum,count):
    res=-1
    if(index<0):
        return count
    
    if(boxes[index].str>=weight_sum):
        res=get_max_seq(index-1,weight_sum+boxes[index].weight,count+1)

    res=max(res,get_max_seq(index-1,weight_sum,count))
    return res

def dyna(boxes,N):
    print('boxes: ',boxes)
    INF=int(1e10+7)
    dp=[INF]*(N+1)
    dp[0]=0
    # print('dp: ',dp)

    for  i in range(0,N):
        for j in range(i,-1,-1):

            if(dp[j]<=boxes[i].str):
                dp[j+1]=min(dp[j+1],dp[j] + boxes[i].weight)

    # print('dp: ',dp)

    for i in range(N,-1,-1):
        if(dp[i]!=INF):
            return i
    

# b_o=[(1,3),(3,4),(2,3),(5,6),(3,5),(8,7),(4,6)]
#boxes= [ Boxes(x[0],x[1]) for x in b_o]

boxes = []
N=int(input())
for _ in range(N):
    a=[ int(x) for x in input().split()]
    boxes.append(Boxes(a[0],a[1]))


# print('input len: ',len(boxes))
# print(boxes)
boxes.sort(key=cmp_to_key(box_cmp),reverse=False)
# print(boxes)
print(get_max_seq(N-1,0,0))
# print(dyna(boxes,N))

Submission status: Runtime Error

Solution code:
N = int(input())

HP= [list(map(int,input().split()))+[_index] for _index in range(N)]
HP.sort()

HP2 = list(HP)
HP2.sort(key=lambda x:(x[1],x[0]))
#if not HP[-1][0]+HP[-1][1] == max(h+p for h,p in HP):
#    raise

def check(_res):
    """
    >>> check([(9, 1), (0, 1)])
    False
    :param _res:
    :return:
    """
    tmp_val = 0
    for h, p, *_ in _res:
        if (tmp_val > h):
            return False
        tmp_val += p

    return True

#print(HP2)
res =[]
for h,p,index in HP2:
   def can_insert(h,p,i):
        _res =list(res)
        _res.insert(i,(h,p))
        return check(_res)
   for i in reversed(range(len(res)+1)):
        if can_insert(h,p,i):
            res.insert(i,(h,p))
            break
    #else:
    #    break

for h,p,index in HP:

print(len(res))

Submission status: Runtime Error

Solution code:
N = int(input())

HP= [list(map(int,input().split())) for _ in range(N)]
HP.sort()

if not HP[-1][0]+HP[-1][1] == max(h+p for h,p in HP):
    raise


def seach(n):
    max_kouho= []
    max_val =-1
    for i in range(N):
        if i in used:
            continue
        h,p= HP[i]
        tmp_val = min(n-p,h)
        if tmp_val>max_val:
            max_kouho = [i]
            max_val=tmp_val
        elif tmp_val==max_val:
            max_kouho.append(i)
    return max_val,max_kouho


used = set([len(HP)-1])
next_val =HP[-1][0]
while next_val>0:
    max_val ,kouho = seach(next_val)

    #print(max_val)
    #print(list(HP[i] for i in kouho))
    if max_val == -1:
        break

    elif len(kouho) >=1:
        next_val=max_val
        used.add(kouho[0])

print(len(used))