Harryxun/stf_run huggingface dataset:
from queue import Queue
h, w = map(int, input().split())
map_list = []
for _ in range(h):
    map_list.append(list(input()))
x_list = [1, 0, -1, 0]
y_list = [0, 1, 0, -1]
black_num = sum([map_list[i].count("#") for i in range(h)])
ans = 0
q = Queue()
q1 = Queue()
for y in range(h):
    for x in range(w):
        if map_list[y][x] == "#":
            q.put([y, x])
while (black_num < (h*w)):
    q_list = []
    for j in range(q.qsize()):
        y, x = q.get()
        if temp[y][x] == "#":
            for i in range(4):
                new_y = y + y_list[i]
                new_x = x + x_list[i]
                if (new_y >= 0) & (new_y < h) & (new_x >= 0) & (new_x < w):
                    if map_list[new_y][new_x] == ".":
                        map_list[new_y][new_x] = "#"
                        black_num += 1
                        q_list.append([new_y, new_x])
    q = Queue()
    for qq in q_list:
        q.put(qq)
    ans += 1
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
from math import ceil
tmp1 = list(map(int,input().split()))
tmp2 = list()
for j in range(5):
    if tmp1[j]%10 == 0:
        tmp2.append(float("inf"))
    else:
        tmp2.append(tmp1[j]%10)
for i in range(5):
    tmp1[i] = ceil(tmp1[i]/10)*10
print(tmp1)
print(tmp2)
print(sum(tmp1)-min(tmp2))

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())
from math import ceil
tmp1 = [A,B,C,D,E]
tmp2 = list()
for j in range(5):
    if tmp1[j]%10 == 0:
        tmp2.append(0)
    else:
        tmp2.append(10 - tmp1[j]%10)
for i in range(5):
    tmp1[i] = ceil(tmp1[i]/10)*10
print(sum(tmp1)-max(tmp2))
a,b,c = map(int,input().split()) 
if b-a == c-b:
	print('YES')
else:
	print('NO')

### FIXED CODE ###

n = int(input())
i = 1

while True:
  if n<2**i:
    break
  else:
    i+=1
print(2**(i-1))
N = int(input())
S = input()

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            fi = S.find(S[i])
            fj = S.find(S[j])
            fk = S.find(S[k])
            if fi >= 0 and fj >= 0 and fk >= 0 and fi < fj and fj < fk:
                ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
S = input()

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            fi = S.find(str(i))
            if fi < 0:
                continue
            fj = S[fi+1:].find(str(j))
            if fj < 0:
                continue
            fk = S[fi+fj+2:].find(str(k))
            if fk < 0:
                continue
            ans += 1

print(ans)
n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
dp = [0]*(n+1)
INF = 1000000007

dp[0] = 1
if 1 not in a:
  dp[1] = 1

for i in range(2,n+1):
    if i not in a :
      dp[i] += dp[i-1] #n-1 段目が安全なら
      dp[i] += dp[i-2] #n-2 段目が安全なら
dp[i] %= INF

print(dp[n])

### FIXED CODE ###

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
dp = [0]*(n+1)
INF = 1000000007

dp[0] = 1
if 1 not in a:
  dp[1] = 1

for i in range(2,n+1):
    if i-1 not in a :
      dp[i] += dp[i-1] #n-1 段目が安全なら
    if i-2 not in a :
      dp[i] += dp[i-2] #n-2 段目が安全なら
    dp[i] %= INF

print(dp[n])
i=input
p=print
s=i()
p=i()
(s+s).count(p) if p('Yes') else p('No')

### FIXED CODE ###

s=input()
p=input()
print('Yes'if p in s*2 else'No')
N = int(input())
S = input()

prev = None
count = 0

for i in S:
  if prev != i:
  	prev = i
    count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = input()

prev = None
count = 0

for i in S:
  if prev != i:
    prev = i
    count += 1
    
print(count)
k,n=map(int,input())
l=list(map(int,input()))
v=[k-l[-1]+l[0]]
for i in range(n-1):
  v.append(l[i+1]-l[i])
v.sort()
print(k-v[-1])

### FIXED CODE ###

k,n=map(int,input().split())
l=list(map(int,input().split()))
v=[k-l[-1]+l[0]]
for i in range(n-1):
  v.append(l[i+1]-l[i])
v.sort()
print(k-v[-1])
n,d=map(int,input().split())

ans=0

for i in range(n):

	a,b=map(int,input().split())	if a*a+b*b<=d*d:ans+=1

print(ans)

### FIXED CODE ###

n,d=map(int,input().split())
ans=0
for i in range(n):
	a,b=map(int,input().split())
	if a*a+b*b<=d*d:ans+=1
print(ans)
# -*- coding: utf-8 -*-

tmp=list(map(int,input().split()))
tmp_list.sort()
K=int(input())
ans=tmp[0]+tmp[1]+(tmp[2]*(2**K))
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

tmp=list(map(int,input().split()))
tmp.sort()
K=int(input())
ans=tmp[0]+tmp[1]+(tmp[2]*(2**K))
print(ans)
if __name__ == '__main__':
    X, Y = map(int, input().split())

    print(int(X + y/2))



### FIXED CODE ###

if __name__ == '__main__':
    X, Y = map(int, input().split())

    print(int(X+Y/2))
N = int(input())
A = [int(x) for x in input().split()]
p = []
m = []
for a in A:
    if a < 0:
        m.append(a)
    else:
        p.append(a)
was = []
if N == 2:
    print(max(A)-min(A))
    print(max(A), min(A))
    quit()
p.sort()
if len(m) == 0:
    m.append(p[-1] - p[0])
    was.append((p[-1], p[0]))
    p = p[1:-1]

mm = m[0]
m = m[1:]
pp = p[0]
p = p[1:]
for x in p:
    was.append((mm,x))
    mm -= x
for x in m:
    was.append((pp,x))
    pp -= x
was.append((pp, mm))
print(pp-mm)
for p,m in was:
    print(p,m)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
p = []
m = []
for a in A:
    if a < 0:
        m.append(a)
    else:
        p.append(a)
was = []
if N == 2:
    print(max(A)-min(A))
    print(max(A), min(A))
    quit()
if len(m) == 0:
    p.sort()
    m.append(p[0] - p[-1])
    was.append((p[0], p[-1]))
    p = p[1:-1]
elif len(p) == 0:
    m.sort()
    p.append(m[-1] - m[0])
    was.append((m[-1], m[0]))
    m = m[1:-1]

mm = m[0]
m = m[1:]
pp = p[0]
p = p[1:]
for x in p:
    was.append((mm,x))
    mm -= x
for x in m:
    was.append((pp,x))
    pp -= x
was.append((pp, mm))
print(pp-mm)
for p,m in was:
    print(p,m)
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(int)>
using namespace std;
#define All(v) (v).begin(),(v).end()
const long long mod = 1000000007;
const long long inf = mod*mod;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
signed main(){
    int a,b,c;
    cin >> a >> b >> c;
    cout << max(c - a + b, 0) << endl;
}

### FIXED CODE ###

a, b, c = map(int, input().split())
print(max(c-(a-b),0))
class a(object):
    def __init__(self, buf_size=10000):
        self.m = [None for _ in range(buf_size)]
        self.ind = 0
        self.cur = 0

    def enqueue(self, elem):
        self.m[self.ind] = elem
        self.ind += 1

    def dequeue(self):
        if self.is_empty(): raise EOFError('this queue is empty')
        result = self.m[self.cur]
        self.cur += 1
        return result

    def is_empty(self):
        return self.ind <=\
               self.cur

n, q = input().split()
qe = a(n)
cur_time = 0

for _ in range(int(n)):
    name, time = input().split()
    qe.enqueue((name, int(time)))

while not qe.is_empty():
    name, time = qe.dequeue()
    if time > int(q):
        cur_time += int(q)
        time -= int(q)
        qe.enqueue((name, time))
    else:
        cur_time += int(time)
        print('{} {}'.format(name, cur_time))



### FIXED CODE ###

class a(object):
    def __init__(self, buf_size=10000000):
        self.m = [None for _ in range(buf_size)]
        self.ind = 0
        self.cur = 0

    def enqueue(self, elem):
        self.m[self.ind] = elem
        self.ind += 1

    def dequeue(self):
        if self.is_empty(): raise EOFError('this queue is empty')
        result = self.m[self.cur]
        self.cur += 1
        return result

    def is_empty(self):
        return self.ind <= self.cur

n, q = input().split()
qe = a()
cur_time = 0

for _ in range(int(n)):
    name, time = input().split()
    qe.enqueue((name, int(time)))

while not qe.is_empty():
    name, time = qe.dequeue()
    if time > int(q):
        cur_time += int(q)
        time -= int(q)
        qe.enqueue((name, time))
    else:
        cur_time += int(time)
        print('{} {}'.format(name, cur_time))
N, Q=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(N-1)]
px=[list(map(int, input().split())) for _ in range(Q)]
to=[[] for _ in range(N)]
co=[0 for _ in range(N)]

for a, b in ab:
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
for p, x in px:
    p-=1
    co[p]+=x

def dfs(v, p=-1):
    for u in to[v]:
        if p==u:
            continue
        co[u]+=co[v]
        dfs(u, v)

dfs(0)
print(*co)

### FIXED CODE ###

N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
node_lst=sorted(node_lst, key=lambda x:x[0])
for l in node_lst:
    src, dst = l[0]-1, l[1]-1
    cnt_lst[dst]+=cnt_lst[src]
print(" ".join([str(c) for c in cnt_lst]))
import numpy as np

N, M = map(int, input().split())
a = np.array(list(map(int, input().split())))

if N == 1:
    for i in range(M):
        a //= 2
    print(a[0])
    exit()

a.sort()
cur = M - 1
for i in range(M):
    if i == 0:
        a[-1] //= 2
    else:
        if (a[cur-1] > a[cur]):
            cur -= 1
            a[a[cur:].argmax()+cur] //= 2
        else:
            a[-1] //= 2
print(sum(a))

### FIXED CODE ###

import heapq

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

q = []
for i in range(N):
    # 最も大きい値を取り出して1/2したいので、ここで反転させておき、最終的に足す時に戻す
    heapq.heappush(q, -a[i])
for i in range(M):
    l = heapq.heappop(q)
    heapq.heappush(q, -(-l//2))
print(-sum(q))
import itertools

n, m = map(int, input().split())

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

x = 0
li_a = []

while a[x][0]== 1:
    li_a.append(a[x][1])
    x += 1

a.sort(reverse=True, key=lambda x: x[1])

x = 0
li_b = []

while a[x][1] == n:
    li_b.append(a[x][0])
    x += 1

print("POSSIBLE" if set(li_a) & set(li_b) else "IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

x = 0
li_a = []

while x < m and a[x][0]== 1:
    li_a.append(a[x][1])
    x += 1

a.sort(reverse=True, key=lambda x: x[1])

x = 0
li_b = []

while x < m and a[x][1] == n:
    li_b.append(a[x][0])
    x += 1

print("POSSIBLE" if set(li_a) & set(li_b) else "IMPOSSIBLE")
import sys
from collections import deque

def bfs(maze, visited):
    try:
        sy,sx=0,0
        gy,gx=H-1,W-1
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]

            p=[]
            if x>0 : p.append([0,-1])
            if x<W-1: p.append([0,1])
            if y>0: p.append([-1,0])
            if y<H-1: p.append([1,0])
            for j, k in p:
                new_y, new_x = y+j, x+k
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])

    except RuntimeError:
        print(-1)
        sys.exit()


H,W=map(int,input().split())
m=[input() for i in range(H)]

ans=0
for i in range(H):
    for j in range(W):
        if m[i][j]==".": ans+=1

visited=[[-1]*W for i in range(H)]
try:
    print(ans-bfs(m,visited)-1)
except RuntimeError:
    print(-1)
    sys.exit()

### FIXED CODE ###

import sys
from collections import deque

def bfs(maze, visited):
    try:
        sy,sx=0,0
        gy,gx=H-1,W-1
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]

            p=[]
            if x>0 : p.append([0,-1])
            if x<W-1: p.append([0,1])
            if y>0: p.append([-1,0])
            if y<H-1: p.append([1,0])
            for j, k in p:
                new_y, new_x = y+j, x+k
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
        return -1

    except RuntimeError:
        print(-1)
        sys.exit()


H,W=map(int,input().split())
m=[input() for i in range(H)]

ans=0
for i in range(H):
    for j in range(W):
        if m[i][j]==".": ans+=1

visited=[[-1]*W for i in range(H)]
p=bfs(m,visited)
print( p if p==-1 else ans-p-1)
x=input()
print(x^3)

### FIXED CODE ###

x=int(input())
print(x**3)
h,w=map(int,input().split())
s=[input for i in range(h)]
for i in range(h):
    l=""
    for j in range(w):
        if s[i][j]=="#":
            l+="#"
        else:
            l+=str(sum([t[max(0,j-1):min(w,j+2)].count("#") for t in s[max(0,i-1):min(h,i+2)]]))
    print(l)    
            


### FIXED CODE ###

def minesweeper(grid, x, y):
    if grid[x][y] == '.':
        cnt = 0
        for i in range(x-1, x+2): 
            if i < 0 or H-1 < i:
                pass
            else :
                for j in range(y-1, y+2):
                    if j < 0 or W - 1 < j:
                        pass
                    else :
                        if grid[i][j] == '#':
                            cnt += 1
        grid[x][y] = str(cnt)
    return grid


H, W = [int(i) for i in input().split()]

grid = []
for h in range(H):
    grid.append([l for l in input()])
    
for x in range(H):
    for y in range(W):
        grid = minesweeper(grid, x, y)
        
for row in grid:
    print(''.join(row))
n, k, x, y = [(int(input()), for i in range(4))]
print(x*n - (x - y)*max(0, n-k))


### FIXED CODE ###

n,k,x,y=[int(input()) for i in range(4)]
print(n*x-(x-y)*max(n-k,0))
N, M = map(int, input().split())
E = []
for i in range(M):
    a, b = map(int, input().split())
    E.append((a-1, b-1))

tree = {n: n for n in range(N)}
child = {n: 1 for n in range(N)}

max_connection = N*(N-1)//2


def find_head(i):
    if tree[i] != i:
        return find_head(tree[i])
    else:
        return i


connection = 0
out_list = [max_connection]
for e in E[:0:-1]:
    head_e0 = find_head(e[0])
    head_e1 = find_head(e[1])

    if head_e0 == head_e1:
        out_list.append(max_connection-connection)
    else:
        tree[head_e1] = head_e0
        connection = connection + child[head_e0]*child[head_e1]
        child[head_e0] += child[head_e1]
        out_list.append(max_connection - connection)

for o in out_list[::-1]:
    print(o)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
E = []
for i in range(M):
    a, b = map(int, input().split())
    E.append((a-1, b-1))

tree = {n: n for n in range(N)}
child = {n: 1 for n in range(N)}

max_connection = N*(N-1)//2


def find_head(i):
    if tree[i] != i:
        tree[i] = find_head(tree[i])
        return tree[i]
    else:
        return i


connection = 0
out_list = [max_connection]
for e in E[:0:-1]:
    head_e0 = find_head(e[0])
    head_e1 = find_head(e[1])

    if head_e0 == head_e1:
        out_list.append(max_connection-connection)
    else:
        tree[head_e1] = head_e0
        connection = connection + child[head_e0]*child[head_e1]
        child[head_e0] += child[head_e1]
        out_list.append(max_connection - connection)
    if max_connection == connection:
        break

if len(out_list) != M:
    out_list += [0]*(M-len(out_list))

for o in out_list[::-1]:
    print(o)
n = int(input())
a = list(map(int, input().split()))
b = set(a)

def choose2(x):
    return int(x*(x-1)/2)
    
total = 0
for i in b:
    total += choose2(a.count(i))

for i in a:
    print(total - choose2(s[i]) + choose2(s[i]-1))

### FIXED CODE ###


n = int(input())
a = list(map(int, input().split()))

from collections import Counter
count = Counter(a)

def choose2(x):
    return int(x*(x-1)/2)
    
total = 0
for i in list(count.values()):
    total += choose2(i)

for i in a:
    s = count[i]
    print(total - choose2(s) + choose2(s-1))
def main():
    import sys
    input = sys.stdin.readline
    
    a,b = map(int,input().split())

    def make_two_divisors(a,b):
        lower_divisors,upper_divisors = [],[]
        prime_li = [True]*(max(a,b)+1)
        i = 1
        while i*i<=max(a,b):
            if prime_li[i]:
                if a%i==0 and b%i==0:
                    lower_divisors.append(i)
                    #if i != max(a,b)//i and a%(max(a,b)//i)==0 and b%(max(a,b)//i)==0:
                    #    upper_divisors.append(b//i)
                    if i!=1:
                        for j in range(i+i,max(a,b),i):
                            prime_li[j]=False 
            i+=1
        return lower_divisors
    print(len(make_two_divisors(a,b)))

if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    
    a,b = map(int,input().split())

    #gcd(a,b)の素因数分解
    import math
    gcd = math.gcd(a,b)

    p = []
    for i in range(2,int(math.sqrt(gcd))+1):
        while gcd % i == 0:
            gcd /= i
            p.append(i)
            
    p.append(int(gcd))
    p.append(1)
    print(len(list(set(p))))

if __name__=='__main__':
    main()
n=int(input())
c=0
from itertools import combinations 
def rSubset(arr, r): 
  
    # return list of all subsets of length r 
    # to deal with duplicate subsets use  
    # set(list(combinations(arr, r))) 
    return list(combinations(arr, r)) 
for y in range(1,n+1):
    for i in range(1,int(y**0.5)):
        for j in range(1,int(y**0.5)):
            if(3*i*i+j*j+2*i*j==y):
                if(i==j):
                  c=c+1
                else:
                   c=c+3
    print(c)
if(c==0): 
  for i in range(1,int(y**0.5)):
        t.append(y)
  x=rSubset(t,3)
  for i in range(len(x)):
        if(x[i][0]**2+x[i][1]**2+x[i][2]**2+x[i][0]*x[i][1]+x[i][0]*x[i][2]+x[i][1]*x[i][2]==n):
           c=c+6
  print(c)
    

### FIXED CODE ###

N = int(input())

ans = [0]*N

for i in range(1,101,1):
  for j in range(1,101,1):
    for k in range(1,101,1):
      n = i**2+j**2+k**2+i*j+j*k+k*i
      if n > N:
        continue
      else:
        ans[n-1]+=1
      
for i in range(N):
  print(ans[i])
A,B,C = input()
if A == B == C:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

A,B,C = input().split()
if A == B == C:
  print('Yes')
else:
  print('No')
from operator import mul
from functools import reduce

mod = 10**9+7
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under % mod


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

for i in range(1, K+1):
    ans = cmb(N - K + 1, i) * cmb(K - 1, i - 1) % mod
    print(ans)

### FIXED CODE ###

from math import factorial
 
def cmb(n, r):
  return factorial(n) // (factorial(n - r) * factorial(r))


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

for i in range(1, K+1):
    try:
        ans = cmb(N - K + 1, i) * cmb(K - 1, i - 1) % (10**9+7)
        print(ans)
    except:
        print(0)
import sys,gc

    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(s[7:])
        fp += 1
    elif s[6] == ' ':
        i=-1
        try:
            while True:
                i = A[i+1:].index(s[7:])
        finally:
            if i!=-1:
                del A[i]
                fp -=1
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        A[bp]=-1
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    if e!=-1:
        print int(e),

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
    weight, value = map(int,input().split())
    w.append(weight)
    v.append(value)
dp = [[0 for _ in range(10*5*100)] for _ in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if sum_w -w[i] >=0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w-w[i]] + v[i])
        dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w])
print(dp[N][W])

### FIXED CODE ###

n,w=map(int,input().split())
weight,value=[0]*110,[0]*110
dp = [[0 for _ in range(100100)] for _ in range(110)]
for i in range(n):
    weight[i],value[i] = map(int,input().split())
for i in range(n):
    sum_w =0
    while sum_w <= w:
        #i番目の品物を選ぶ
        if(sum_w - weight[i] >=0):
            dp[i+1][sum_w] =max(dp[i+1][sum_w], dp[i][sum_w - weight[i]]+ value[i])
        #選ばない場合
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
        sum_w +=1
print(dp[n][w])
N = int(input("Number:\n"))
if(N%2==):
  res = (N/2)/N
else:
  res = ((N+1)/2)/N
print(res)

### FIXED CODE ###

N = int(input())
if(N%2==0):
  print((N/2)/N)
else:
  print(((N+1)/2)/N)
N, M = map(int, input().split())
left=0
right=0

for i in range(N):
    L, R = map(int, input().split())
    if L > left:
        left = L
    if R < left:
        right = R

if left <= right:
    print(right-left+1)
else:
    print(0)

### FIXED CODE ###

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

left = []
right= []

for i in range(M):
    L, R = map(int, input().split())
    left.append(L)
    right.append(R)

l = max(left)
r = min(right)

if l <= r:
    print(r-l+1)
else:
    print(0)
import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M = map(int,input().split())
    q = list(map(int, input().split()))
    total = sum(q)
    heapq.heapify(q)

    for i in range(M):
        B, C = map(int,input().split())
        for j in range(B):
            tmp = heapq.heappop(q)
            if tmp < C:
                heapq.heappush(C)
                total += (C - tmp)
            else:
                heapq.heappush(tmp)
                break

    print(total)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M = map(int,input().split())
    q = list(map(int, input().split()))
    X = [list(map(int,input().split())) for _ in range(M)]
    X.sort(key=lambda x:-x[1])
    total = sum(q)
    heapq.heapify(q)

    for i in range(M):
        for j in range(X[i][0]):
            tmp = heapq.heappushpop(q, X[i][1])
            if tmp < X[i][1]:
                total += (X[i][1] - tmp)
            else:
                break

    print(total)

if __name__ == "__main__":
    main()