Problem p03038 (python)

Fixed submission:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]


# In[14]:


"""
def binary_search(nbs, tar):
    #print(nbs, tar)
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln < rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値がtarより大きければ、
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t
"""


# In[16]:


sbcs = sorted(bcs, key=lambda x:x[1], reverse=True)
sA = sorted(A)

nb = 0
ans = 0
is_finish = False

for i in range(M):
    B, C = sbcs[i]
    
    for j in range(B):
        if nb < N and sA[nb] < C:
            ans += C
            nb += 1
        else:
            is_finish = True
            break
    
    if is_finish:
        break

if nb < N:
    ans += sum(sA[nb:])

print(ans)
        
"""
    if nb >= N: # nbがN以上になれば、終了
        break
    
    B, C = sbcs[i]
    las = nb+B-1
    las = las if las <N else N-1
    if sA[nb] >= C: # もしnb個目がC以上であれば、終了
        break
    elif sA[nb+B-1] <= C: #もしB個目が、C以下なら、B個目までをCにする
        sA[nb:nb+B] = [C]*B
        nb += B
    else: #nb個目がC未満で、nb+B-1個目がCより大きければ
        t = binary_search(sA[nb:nb+B], C) 
        t = t if nb+t < N else N-nb-1
        sA[nb:nb+t+1] = [C]*(t+1)
        nb += t+1
    
print(sum(sA))
"""


# In[ ]:

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]


# In[14]:


"""
def binary_search(nbs, tar):
    #print(nbs, tar)
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln < rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値がtarより大きければ、
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t
"""


# In[16]:


sbcs = sorted(bcs, key=lambda x:x[1], reverse=True)
sA = sorted(A)

nb = 0
ans = 0
is_finish = False

for i in range(M):
    B, C = sbcs[i]
    
    for j in range(B):
        if nb < N and A[nb+i] < C:
            ans += C
            nb += 1
        else:
            is_finish = True
            break
    
    if is_finish:
        break

if nb < N:
    ans += sum(A[nb:])

print(ans)
        
"""
    if nb >= N: # nbがN以上になれば、終了
        break
    
    B, C = sbcs[i]
    las = nb+B-1
    las = las if las <N else N-1
    if sA[nb] >= C: # もしnb個目がC以上であれば、終了
        break
    elif sA[nb+B-1] <= C: #もしB個目が、C以下なら、B個目までをCにする
        sA[nb:nb+B] = [C]*B
        nb += B
    else: #nb個目がC未満で、nb+B-1個目がCより大きければ
        t = binary_search(sA[nb:nb+B], C) 
        t = t if nb+t < N else N-nb-1
        sA[nb:nb+t+1] = [C]*(t+1)
        nb += t+1
    
print(sum(sA))
"""


# In[ ]:

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]
"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
"""


# In[14]:


def binary_search(nbs, tar):
    #print(nbs, tar)
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln < rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値が
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t


# In[16]:


sbcs = sorted(bcs, key=lambda x:x[1], reverse=True)
nb = 0
sA = sorted(A)
for i in range(M):
    if nb >= N: # nbがN以上になれば、終了
        break
    
    B, C = sbcs[i]
    las = nb+B-1
    las = las if las <N else N-1
    if sA[nb] >= C: # もしnb個目がC以上であれば、終了
        break
    elif sA[nb+B-1] <= C: #もしB個目が、C以下なら、B個目までをCにする
        sA[nb:nb+B] = [C]*B
        nb += B
    else: #nb個目がC未満で、nb+B-1個目がCより大きければ
        t = binary_search(sA[nb:nb+B], C) 
        t = t if nb+t < N else N-nb-1
        sA[nb:nb+t+1] = [C]*(t+1)
        nb += t+1
    
print(sum(sA))


# In[ ]:

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]
"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
"""


# In[14]:


def binary_search(nbs, tar):
    #print(nbs, tar)
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln < rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値が
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t


# In[16]:


sbcs = sorted(bcs, key=lambda x:x[1], reverse=True)
nb = 0
sA = sorted(A)
for i in range(M):
    if nb >= N: # nbがN以上になれば、終了
        break
    
    B, C = sbcs[i]
    if sA[nb] >= C: # もしnb個目がC以上であれば、終了
        break
    elif sA[nb+B-1] <= C: #もしB個目が、C以下なら、B個目までをCにする
        sA[nb:nb+B] = [C]*B
        nb += B
    else: #nb個目がC未満で、nb+B-1個目がCより大きければ
        t = binary_search(sA[nb:nb+B], C) 
        t = t if nb+t < N else N-nb-1
        sA[nb:nb+t+1] = [C]*(t+1)
        nb += t+1
    
print(sum(sA))


# In[ ]:

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]
"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
"""


# In[14]:


def binary_search(nbs, tar):
    #print(nbs, tar)
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln < rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値が
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t


# In[16]:


sbcs = sorted(bcs, key=lambda x:x[1], reverse=True)
nb = 0
sA = sorted(A)
for i in range(M):
    if nb >= N: # nbがN以上になれば、終了
        break
    
    B, C = sbcs[i]
    if sA[nb] >= C: # もしnb個目がC以上であれば、終了
        break
    elif sA[nb+B-1] <= C: #もしB個目が、C以下なら、B個目までをCにする
        sA[nb:nb+B] = [C]*B
        nb += B
    else: #nb個目がC未満で、nb+B-1個目がCより大きければ
        t = binary_search(sA[nb:nb+B], C) 
        t = t if nb+t < N else N-1
        sA[nb:nb+t+1] = [C]*(t+1)
        nb += t+1
    
print(sum(sA))


# In[ ]:

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]
"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
"""


# In[14]:


def binary_search(nbs, tar):
    #print(nbs, tar)
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln < rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値が
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t


# In[16]:


sbcs = sorted(bcs, key=lambda x:x[1], reverse=True)
nb = 0
sA = sorted(A)
for i in range(M):
    if nb >= N: # nbがN以上になれば、終了
        break
    
    B, C = sbcs[i]
    if sA[nb] >= C: # もしnb個目がC以上であれば、終了
        break
    elif sA[nb+B-1] <= C: #もしB個目が、C以下なら、B個目までをCにする
        sA[nb:nb+B] = [C]*B
        nb += B
    else: #nb個目がC未満で、nb+B-1個目がCより大きければ
        t = binary_search(sA[nb:nb+B], C) if nb+t < N else N-1
        sA[nb:nb+t+1] = [C]*(t+1)
        nb += t+1
    
print(sum(sA))


# In[ ]:

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]
"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
"""


# In[14]:


def binary_search(nbs, tar):
    #print(nbs, tar)
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln < rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値が
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t


# In[16]:


sbcs = sorted(bcs, key=lambda x:x[1], reverse=True)
nb = 0
sA = sorted(A)
#print(sA)
#print(sbcs)
for i in range(M):
    if nb >= N: # nbがN以上になれば、終了
        break
    
    B, C = sbcs[i]
    #print(B, C, nb)
    if sA[nb] >= C: # もしnb個目がCより大きければ、終了
        break
    if sA[nb+B-1] <= C: #もしB個目が、Cより小さければ、B個目までをCにする
        sA[nb:nb+B] = [C]*B
        nb += B
        continue
    
    t = binary_search(sA[nb:nb+B], C)
    #print(t)
    sA[nb:nb+t+1] = [C]*(t+1)
    nb += t+1
#print(sA)
print(sum(sA))


# In[ ]:

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]
"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
"""


# In[32]:


#print(N, M)
#print(A)
#print(bcs)


# In[14]:


def binary_search(nbs, tar):
    #print(nbs, tar)
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln < rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値が
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t


# In[15]:


sbcs = sorted(bcs, key=lambda x:x[1], reverse=True)
nb = 0
sA = sorted(A)
#print(sA)
#print(sbcs)
for i in range(M):
    if nb >= N: # nbがN以上になれば、終了
        break
    
    B, C = sbcs[i]
    #print(B, C, nb)
    if sA[nb] >= C: # もしnb個目がCより大きければ、終了
        break
    if sA[nb+B-1] < C: #もしB個目が、Cより小さければ、B個目までをCにする
        sA[nb:nb+B] = [C]*B
        nb += B
        continue
    
    t = binary_search(sA[nb:nb+B], C)
    #print(t)
    sA[nb:nb+t+1] = [C]*(t+1)
    nb += t+1
#print(sA)
print(sum(sA))


# In[ ]:

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]
"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
"""


# In[32]:


#print(N, M)
#print(A)
#print(bcs)


# In[14]:


def binary_search(nbs, tar):
    #print(nbs, tar)
    
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln<=rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値が
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t


# In[15]:


sbcs = sorted(bcs, key=lambda x:x[1], reverse=True)
nb = 0
sA = sorted(A)
#print(sA)
#print(sbcs)
for i in range(M):
    if nb >= N:
        break
    
    B, C = sbcs[i]
    #print(B, C, nb)
    if sA[nb] >= C:
        continue
    if sA[nb+B-1] < C: #もしB個目が、Cより小さければ、B個目までをCにする
        sA[nb:nb+B] = [C]*B
        nb += B
        continue
    t = binary_search(sA[nb:nb+B], C)
    #print(t)
    sA[nb:nb+t+1] = [C]*(t+1)
    nb += t+1
#print(sA)
print(sum(sA))


# In[ ]:

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# coding: utf-8

# In[31]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]
"""
3 2
5 1 4
2 3
1 5
"""


# In[32]:


#print(N, M)
#print(A)
#print(bcs)


# In[33]:


def binary_search(nbs, tar):
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln<=rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値が
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t


# In[34]:


bcs = sorted(bcs, key=lambda x:x[1], reverse=True)
nb = 0
A = sorted(A)
#print(A)
#print(bcs)
for i in range(M):
    B, C = bcs[i]
    #print(B, C, nb)
    if A[nb] >= C:
        continue
    if A[nb+B-1] < C: #もしB個目が、Cより小さければ、B個目までをCにする
        A[nb:nb+B] = [C]*B
        nb += B
        continue
    t = binary_search(A[nb:nb+B], C)
    A[nb:nb+t] = [C]*t
    nb += t
#print(A)
print(sum(A))


# In[ ]: