Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n, m = map(int, input().split())
X = [int(x) for x in input().split()]
Y = [int(x) for x in input().split()]
p = 10 ** 9 + 7
S = [[(X[i + 1] - X[i]) * (Y[j + 1] - Y[j]) for j in range(m - 1)] for i in range(n - 1)]
for i in range(n - 1):
  for j in range(m - 1):
    S[i][j] *= (n - i - 1) * (i + 1)
    S[i][j] %= p
    S[i][j] *= (m - j - 1) * (j + 1)
    S[i][j] %= p
print(sum([sum(s) for s in S]) % p)

### FIXED CODE ###

n, m = map(int, input().split())
p = 10 ** 9 + 7
X = [int(x) for x in input().split()]
Y = [int(x) for x in input().split()]
XX = [(X[i + 1] - X[i]) * (n - i - 1) * (i + 1) % p for i in range(n - 1)]
YY = [(Y[j + 1] - Y[j]) * (m - j - 1) * (j + 1) % p for j in range(m - 1)]
print(sum(XX) * sum(YY) % p)
### BUGGY CODE ###

N, M = map(int,input().split())
A = sorted(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key = lambda x: -x[1])

for B, C in BC:
  B -= 1
  t = False
  for a in A[:B+1]:
    if a > C:
      B -= 1
      if B < 0:
        t = True
        break
  if t:
    continue
  A = A[B+1:] + [C]*(B+1)
print(sum(A))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key = lambda x: -x[1])

for B, C in BC:
  A.extend([C]*B)
  if len(A) > N*2:
    break
A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

n,k,q = map(lambda x: int(x), input().split())
a = []
score = [k]*n
for i in range(q):
    a.append(int(input()))

for i in a:
    score[i-1] += 1
    score = list(map(lambda y: y-1,score))

for i in score :
    if i > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

n,k,q = map(lambda x: int(x), input().split())
a = []
score = [k-q]*n
for i in range(q):
    a.append(int(input()))

for i in a:
    score[i-1] += 1

for i in score :
    if i > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n,m=[int(s) for s in input().split()]
key=[]
for i in range(m):
  cost,b=[int(s) for s in input().split()]
  op=0
  for i in input().split():
    op+=1<<(int(i)-1)
  key.append([cost,op])
N=2**n
dp=[[10**7 for _ in range(N)] for _ in range(m)]
dp[0][key[0][1]]=key[0][0]
for i in range(1,m):
  for j in range(N):
    dp[i][j]=dp[i-1][j]
  dp[i][key[i][1]]=min([dp[i-1][key[i][1]],key[i][0]])
  for j in range(N):
    x=j|key[i][1]
    if dp[i][x]!=-1:
      dp[i][x]=min([dp[i][x],dp[i-1][j]+key[i][0]])
if dp[m-1][N-1]==10**7:
  print(-1)
else:
  print(dp[m-1][N-1])

### FIXED CODE ###

n,m=[int(s) for s in input().split()]
key=[]
for i in range(m):
  cost,b=[int(s) for s in input().split()]
  op=0
  for i in input().split():
    op+=1<<(int(i)-1)
  key.append([cost,op])
N=2**n
dp=[[10**7 for _ in range(N)] for _ in range(m)]
dp[0][key[0][1]]=key[0][0]
dp[0][0]=0
for i in range(1,m):
  for j in range(N):
    dp[i][j]=min([dp[i-1][j],dp[i][j]])
    x=j|key[i][1]
    dp[i][x]=min([dp[i][x],dp[i-1][j]+key[i][0]])
if dp[m-1][N-1]==10**7:
  print(-1)
else:
  print(dp[m-1][N-1])
### BUGGY CODE ###

S = input()
Q = int(input())
qs = list(input() for _ in range(Q))
for q in qs:
    q = q.split()
    if q[0] == '1':
        S = S[::-1]
    else:
        if q[1] == '1':
            S = q[2] + S
        else:
            S = S + q[2]
print(S)

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
S = deque(input())
rev = False
apdlft = S.appendleft
apd = S.append

for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            apdlft(q[2])
        else:
            apd(q[2])

if rev:
    print((''.join(S))[::-1])
else:
    print(''.join(S))
### BUGGY CODE ###

import collections
from sys import stdin


def get_result(data):
    S = data[0]
    int_S = int(S)
    mod_all_bit = [0]
    for i in range(len(S)):
        mod_all_bit.append(int_S % (10**(i+1)) % 2019)
    c = collections.Counter(mod_all_bit)
    ans = 0
    for key, val in c.items():
        if val >= 2:
            ans += int(val * (val-1) * 0.5)
    return ans


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin


def get_result(data):
    S = data[0]
    mod_all_bit = [0] * 2019
    mod_all_bit[0] = 1
    # 10**i の mod を漸化式的に事前計算
    # こうすることで計算が効率化できる
    ten_i_mod = [0] * len(S)
    ten_i_mod[0] = 1
    for i in range(len(S)-1):
        ten_i_mod[i+1] = (ten_i_mod[i] * 10) % 2019
    mod = 0
    for i in range(len(S)):
        mod = (mod + ten_i_mod[i] * int(S[-(i+1)])) % 2019
        mod_all_bit[mod] += 1
    ans = 0
    for val in mod_all_bit:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))

cnt = 0
tmp = []
for i in range(N):
    for j in range(N):
        if P[i] - 1 <= P[j] <= P[i] + 1:
            cnt += 1
    tmp.append(cnt)
    cnt = 0

print(max(tmp))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
ans = [0] * (max(A) + 2)
 
for a in A:
    if a == 0:
        ans[a] += 1
        ans[a + 1] += 1
    if a != 0:
        ans[a - 1] += 1
        ans[a] += 1
        ans[a + 1] += 1
print(max(ans))
### BUGGY CODE ###

N = int(input())
aA=[int(_) for _ in input().split()]
iMin = min(aA)
iMax = max(aA)


def ggg(i,j):
    if i < j :
        i,j = j,i
    i %= j
    if i == 0:
        return j
    else:
        return ggg(j,i)

if iMin  == 1:
    print(1)
else:
    iDm = [i % iMin for i in aA]
    if max(iDm) == 0:
        print(iMin)
        exit()
    else:
        iM = iMax
        for i in range(N):
            iA = aA[i]
            for j in range(i+1,N):
                iMt = ggg(iA,aA[j])
                if 0 < iMt and iMt < iM:
                    iM = iMt
                if iM == 1:
                    print(1)
                    exit()
        print(iM)


### FIXED CODE ###

#gcdか....
def fgcd(a,b):
    while b:
        a,b = b,a%b
    return a

N = int(input())
aA = sorted(set(int(_) for _ in input().split()))
b = aA[0]
for a in aA[1:]:
    b = fgcd(a,b)
print(b)
### BUGGY CODE ###

import copy

N = int(input())
X = list(map(int, input().split()))
S_X = copy.copy(X)

for i in range(N // 2 + 1):
    for j in range(N - 1 - i):
        if(S_X[j] > S_X[j + 1]):
            tmp = S_X[j + 1]
            S_X[j + 1] = S_X[j]
            S_X[j] = tmp
# s_X = sorted(X)
miX = S_X[N // 2 - 1]
mi1X = S_X[N // 2]
# print(S_X, X)
# print(miX, mi1X)

# print(miX, mi1X)
# print(X)
for a in X:
    if(S_X.index(a) <= N // 2 - 1):
        print(mi1X)
    else:
        print(miX)

### FIXED CODE ###

# import copy

N = int(input())
X = list(map(int, input().split()))
# S_X = copy.copy(X)
S_X = sorted(X)
miX = S_X[N // 2 - 1]
mi1X = S_X[N // 2]
# print(S_X, X)
# print(miX, mi1X)

# print(miX, mi1X)
# print(X)
for a in X:
    if(a <= miX):
        print(mi1X)
    else:
        print(miX)
### BUGGY CODE ###

n=int(input())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
ans=1
for i in range(1,n-1):
    x=1
    tmp=factorization(n-i)
    for j in tmp:
        x*=(j[1]+1)
    ans+=x
        
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n):
    tmp=(n-1)//i
    ans+=tmp
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python

s = raw_input()

s1 = []
for x in s:
	if not s1:
		s1.append(x)
		continue
	if x == 'T' and s1[-1] == 'S':
		s1 = s1[:-1]
	else:
		s1.append(x)

print len(s1)


### FIXED CODE ###

ipt = raw_input()
l = ""
for s in ipt:
    if not l:
        l += s
    elif l[-1]+s == "ST":
        l = l[:-1]
    else:
        l += s
print len(l)
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline

def main():

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

    while M > 0:
        tmp = A.pop()
        tmp = tmp // 2
        bisect.insort_right(A, tmp)
        M -= 1
    print(sum(A))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import heapq
import sys

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = list(map(lambda x: int(x) * (-1), input().split()))
    heapq.heapify(A)

    for _ in range(M):
        tmp = heapq.heappop(A)
        tmp *= -1
        tmp = tmp // 2
        heapq.heappush(A, tmp * (-1))
    print(sum(A) * (-1))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j in d2:
        d2[j] += 1
      else:
        d2[j] = 1
  if len(d2.keys()) == 0:
    continue
  maxb = max(d2.keys())
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
  else:
    d2[maxb] -= 1
print(result)


### FIXED CODE ###

n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)
### BUGGY CODE ###

# coding:utf-8
# Doubly Linked List

class DLL:

    def __init__(self):
        self.array = []

    def insert(self, x):
        self.array = [x] + self.array
    
    def delete(self, x):
        try:
            self.array.remove(x)
        except:
            pass

    def deleteFirst(self):
        del self.array[0]

    def deleteLast(self):
        del self.array[len(self.array)-1]


def main():

    dll = DLL()
    n = int(input())
    ans = ""
    
    for _ in range(n):
        operation = input().split()
        command = operation[0]
        if len(command) == 6:
            key = str(operation[1])
            if command == "insert":
                dll.insert(key)
            else:
                dll.delete(key)

        else:
            if command[6] == 'F':
                dll.deleteFirst()
            else:
                dll.deleteLast()

    for value in dll.array:
        ans += str(value) + " "

    print(ans.rstrip())

if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding:utf-8
# Doubly Linked List

from collections import deque

def main():

    n = int(input())
    dll = deque()

    for _ in range(n):
        operation = input().split(' ')
        if operation[0] in ["insert", "delete"]:
            key = operation[1]
            if operation[0] == "insert":
                dll.appendleft(key)
            else:
                try:
                    dll.remove(key)
                except:
                    pass

        else:
            if operation[0][6] == 'F':
                dll.popleft()

            else:
                dll.pop()

    print(' '.join(dll))

if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
Ar = A[::-1]
Ai = [Ar[i] - A[i] for i in range(N)]
ans = 0

n, r = N-1, K-1 
C = 1
for i in range(N-K, -1, -1):
    ans += Ai[i] * C
    C *= N - i
    if N-K+1 - i != 0:
        C //= N-K+1 - i

print(ans % 1000000007)

### FIXED CODE ###

N, K = map(int, input().split())
MOD = 10**9+7
A = [a % MOD for a in sorted(list(map(int, input().split())))]
MIN, MAX = 0, 0

def div_MOD(a):     # (a^{-1} mod MOD) をフェルマーの小定理より求める
    return pow(a, MOD - 2, MOD)     # a^{-1} = a^{p-2} (mod p)

C = [0]*(K-1) + [1]
for n in range(K, N):
    C.append((C[n-1] * n * div_MOD(n-(K-1))) % MOD)

for i in range(N-K+1):
    MIN = (MIN + (A[i] * C[N-i-1]) % MOD) %MOD
for i in range(N-K+1):
    MAX = (MAX + (A[N-1-i] * C[N-i-1]) % MOD) %MOD

print((MAX - MIN) % MOD)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import fractions
import copy
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())
A = list(map(int, str(input()).split()))

gcds = list()
for i in range(0,N):
    B = copy.deepcopy(A)
    B.pop(i)
    tmp = gcd_list(B)
    gcds.append(tmp)

print(max(gcds))


### FIXED CODE ###

# -*- coding: utf-8 -*-
from fractions import gcd

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))

    L = [0]
    R = [0]

    for i in range(N):
        L.append(gcd(L[-1], A[i]))
    for i in range(N-1, -1, -1):
        R.append(gcd(R[-1], A[i]))

    ans = 0

    for i in range(N):
        ans = max(ans, gcd(L[i], R[N - i - 1]))

    print(ans)
### BUGGY CODE ###

S=list(input())
Q=int(input())
for i in range(Q):  
  L=list(input().split())  
  if L[0]=="1":
    S=list(reversed(S))
  else:
    if L[1]=="1":
      S=list(L[2])+S
    else:
      S=S+list(L[2])
ans=''.join(S)
print(ans)

### FIXED CODE ###

import collections

s = collections.deque(list(input()))
q = int(input())
rev = 0
for i in range(q):
    tfc = list(input().split())
    if tfc[0]=='1':
        rev = abs(rev-1)
    else:
        t,f,c = tfc
        if rev:
            if f=='1':
                s.append(c)
            else:
                s.appendleft(c)
        else:
            if f=='1':
                s.appendleft(c)
            else:
                s.append(c)
if rev:
    t = []
    for i in range(len(s)):
        t.append(s.pop())
    print(''.join(t))
else:
    print(''.join(s))
'''
初期文字列 s が与えられ q 個のクエリを処理した後の文字列を求めます。
10^100回繰り返す根気があるなら自分でやってくれと思わなくもないです。
さて、各クエリではまず t が与えられます。t=1の時文字列を反転させます。
t=2の時はさらに f,c が与えられ、f=1の時文字列の先頭にcを加えます。
f=2の時文字列の末尾にcを加えます。
愚直に行おうとすると文字列の反転で O(len(s))、先頭への追加で 
O(len(s)) かかってしまい間に合いません。
そこでcollections.dequeを利用します。先頭、末尾への追加をO(1) で行えます。
注意する点は反転させると追加する位置が逆になることです。
なので現在の状態を管理しておく必要があります。
同様に出力する時も最終的な向きによって出力する順番が逆になります。
'''
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    import sys
    input = sys.stdin.readline
    h, w, m = map(int, input().split())
    cnt_h = [0] * h
    cnt_w = [0] * w
    bomb = [[False] * w for _ in range(h)]
    for _ in range(m):
        y, x = map(lambda x:int(x) - 1, input().split())
        cnt_h[y] += 1
        cnt_w[x] += 1
        bomb[y][x] = True
        
    kouho_h = []
    max_h = max(cnt_h)
    max_w = max(cnt_w)
    for i in range(h):
        if cnt_h[i] == max_h:
            kouho_h.append(i)
    kouho_w = []
    for i in range(w):
        if cnt_w[i] == max_w:
            kouho_w.append(i)
    
    flag = False
    for i in kouho_h:
        for j in kouho_w:
            if bomb[i][j] == False:
                flag = True
                break
        else:
            continue
        break
    
    if flag:
        print(max_h + max_w)
    else:
        print(max_h + max_w - 1)



if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    h, w, m = map(int, input().split())
    cnt_h = [0] * h
    cnt_w = [0] * w
    bomb = defaultdict(lambda : 0)
    for _ in range(m):
        y, x = map(lambda x:int(x) - 1, input().split())
        cnt_h[y] += 1
        cnt_w[x] += 1
        bomb[(y, x)] = 1
        
    kouho_h = []
    kouho_w = []
    max_h = max(cnt_h)
    max_w = max(cnt_w)
    for i in range(h):
        if cnt_h[i] == max_h:
            kouho_h.append(i)
    for i in range(w):
        if cnt_w[i] == max_w:
            kouho_w.append(i)
    
    for i in kouho_h:
        for j in kouho_w:
            if bomb[(i, j)] == False:
                print(max_h + max_w)
                exit()
    print(max_h + max_w - 1)



if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
from collections import deque

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, dist_all):
    q = deque([[start]])
    q_d = deque([0])
    while(len(q) > 0):
        path = q.popleft()
        dist = q_d.popleft()
        w = path[len(path) - 1]
        for x in adj_list[w]:
            if dist_all[x[0]] is None:
                dist_all[x[0]] = dist + x[1]
                new_path = path[:]
                new_path.append(x[0])
                q.append(new_path)
                q_d.append(dist + x[1])
            elif dist_all[x[0]] != dist + x[1]:
                return False
    return True
dist_all = [None for i in range(n)]
for i in range(n):
    if dist_all[i] is None:
        if not search(i, dist_all):
            print('No')
            exit(0)
print('Yes')

### FIXED CODE ###

import sys
from collections import deque

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, dist_all):
    q = deque([start])
    dist_all[i] = 0
    while(len(q) > 0):
        w = q.popleft()
        for x in adj_list[w]:
            if dist_all[x[0]] is None:
                dist_all[x[0]] = dist_all[w] + x[1]
                q.append(x[0])
            elif dist_all[x[0]] != dist_all[w] + x[1]:
                return False
    return True
dist_all = [None for i in range(n)]
for i in range(n):
    if dist_all[i] is None:
        if not search(i, dist_all):
            print('No')
            exit(0)
print('Yes')
### BUGGY CODE ###

N = int(input())
import numpy as np
#max=int(np.sqrt(N))
for n in range(1,N+1):
    j=0
    max = int(np.sqrt(n))
    for x in range(1,max):
        for y in range(1, max):
            for z in range(1, max):
                if x**2+y**2+z**2+x*y+y*z+z*x==n:
                    #print(x, y, z)
                    #print(f'n:{n}')
                    j+=1
    print(j)

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
	for j in range(1,105):
		for k in range(1,105):
			v = i*i+j*j+k*k+i*j+j*k+k*i;
			if v<10050:
				ans[v]+=1

for i in range(n):
  	print(ans[i+1])
### BUGGY CODE ###

def main():
    s = input()
    n = int(input())
    li = [input().split() for i in range(n)]
    a = 0 #先頭がどっちかという情報

    for x in li:
        if x[0] == "1":
            if a == 0:
                a = 1
            else:
                a = 0
        else:
            if (x[1] == "1" and a == 0) or (x[1] == "2" and a == 1):
                s = x[2] + s
            else:
                s = s + x[2]

    if a == 0: #先頭が前なら
        print(s)
    else: #先頭が後なら
        print(s[::-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

ans = input()
q = int(input())
top = 0
first = str()
last = str()

for i in range(q):
    li =input().split()
    if li[0] =="1":
        top = (top+1)%2
    else:
        if li[1] == "1":
            if top ==0:
                first += li[2]
            else:
                last += li[2]
        else:
            if top ==1:
                first += li[2]
            else:
                last += li[2]

if top == 0:
    ans = first[::-1] + ans + last
else:
    ans = last[::-1] + ans[::-1] + first

print(ans)
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
q = deque()
q.append(0)

ans = [-1 for _ in range(n)]
distance = [float('inf') for _ in range(n)]
distance[0] = 0
ans[0] = 0

visited = set({})

while q:
    start = q.popleft()
    visited.add(start)
    for i in graph[start]:
        distance[i] = min(distance[i], distance[start] + 1)
        if i not in visited:
            q.append(i)
            if (ans[i] == -1):
                ans[i] = start
                
if -1 not in ans:
    print('Yes')
    for i in range(1, n):
        print(ans[i] + 1)
else:
    print('No')


### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
q = deque()
q.append(0)

ans = [-1 for _ in range(n)]
ans[0] = 0

visited = set({})

while q:
    start = q.popleft()
    visited.add(start)
    for i in graph[start]:
        if ans[i] == -1:
            q.append(i)
            ans[i] = start
                
if -1 not in ans:
    print('Yes')
    for i in range(1, n):
        print(ans[i] + 1)
else:
    print('No')
### BUGGY CODE ###

h, n = map(int, input().split())
spells = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 9
dp = [INF] * (h + 1)
dp[0] = 0

for i in range(h):
    for a, b in spells:
        ni = min(i + a, h)
        dp[ni] = min(dp[ni], dp[i] + b)

print(dp[h])

### FIXED CODE ###

h, n = map(int, input().split())
spells = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 9
dp = [INF] * (h + 1)
dp[0] = 0

for i in range(h):
    for a, b in spells:
        ni = min(i + a, h)
        dp[ni] = min(dp[ni], dp[i] + b)

print(dp[h])
### BUGGY CODE ###

n = int(input())
a= input().split()
level = pow(10, 18)
product = 1

for num in range(n):
  product *= int(a[num])

if product > level:
  print("-1")
else:
  print(product)

### FIXED CODE ###

n = int(input())
a= input().split()
level = pow(10, 18)
product = 1

if "0" in a:
  print(0)
else:
  for num in range(n):
    product *= int(a[num])
    if product > level:
      print("-1")
      break
  if product <= level:
    print(product)
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
for i in range(M):
    A[0] = int(A[0] / 2)
    A = sorted(A, reverse=True)
print(sum(A))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = [-int(i) for i in input().split()]
heapq.heapify(A)
for i in range(M):
    a = -int(heapq.heappop(A) / 2)
    heapq.heappush(A, -a)
print(-sum(A))
### BUGGY CODE ###

N=int(input())
H=list(map(int,input().split()))
C=0
for i in range(N):
    for j in range(N-i-1):
        if H[j+i+1]<H[i]-1:
            C=C+1
        else:
            pass
if C==0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
C=0
for i in range(N-1):
    if C>=2:
        break
    elif H[i]>H[i+1]+1:
        C=C+2
        break
    elif H[i]>H[i+1]:
        C=C+1
    elif H[i]<H[i+1]:
        C=0
if C<2:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

a, b, k = map(int, input().split())
data = [i for i in range(a, b + 1)]

ans = []
if k >= -(-len(data)//2):
    for i in data:
        print(i)
else:
    for i in range(k):
        ans.append(data[i])
    for i in range(len(data) - k, len(data)):
        ans.append(data[i])
    for i in ans:
        print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
if k >= -(-(b - a + 1)//2):
    for i in range(a, b + 1):
        print(i)
else:
    for i in range(a, a + k):
        print(i)
    for i in range(b + 1 - k, b + 1):
        print(i)