Harryxun/stf_run huggingface dataset:
h,n = map(int,input().split())
a = []
b = []
for i in range(n):
    x,y= map(int,input().split())
    a.append(x)
    b.append(y)
dp = [[float("inf")]*(h+3) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
    for j in range(h+3):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-a[i]]+b[i])
ans = float("inf")
for i in range(h,h+3):
    ans = min(ans,dp[n][i])

print(ans)

### FIXED CODE ###

h,n = map(int,input().split())
dp = [[float("inf")]*(h+10001) for i in range(n+1)]
dp[0][0]=0

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

    for j in range(h+10001):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-a]+b)
ans = float("inf")
for i in range(h,h+10001):
    ans = min(ans,dp[n][i])

print(ans)
a=(input())
b=(input())

print(a*b,2(a+b))


### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,2*(a+b))
n,m=map(int,input().split())
a=m//n
while True:
  if m/a=int(m/a):
    print(a)
    exit()
  a-=1
  

### FIXED CODE ###

n,m=map(int,input().split())
a=m//n
while True:
  if m/a==int(m/a):
    print(a)
    exit()
  a-=1
N = input()
a = [input() for i in range(N)]
b = [input() for i in range(N)]

sum = 0

for i in range(N):
  if a[i] > b[i]:
    sum += a[i] -b[i]

print(sum)

### FIXED CODE ###

N = int(input())
a = input().split()
b = input().split()

sum = 0

for i in range(N):
  if int(a[i]) > int(b[i]):
    sum += int(a[i]) -int(b[i])

print(sum)
x =int(input())
for i in range(1,10000):
 if x == 0:
  break 
  
 print(case i : x)

### FIXED CODE ###

i = 1

while True:

 x=int(input())
 if x==0:
  break
 print("Case {0}: {1}".format(i,x))
 i+=1
from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

def makeState(state, sign):
    ret = 0
    for s in state:
        ret <<= 1
        if s == sign:
            ret |= 1
    return ret

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        stateX <<= 1
        stateY <<= 1
        if s == 0: N -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1

    cx = costX[stateX]
    cy = costY[stateY]

    cost = sum(min(x, y) for x, y in zip(cx, cy))

    if ans[M] > cost:
        ans[M] = cost

print(*ans, sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
N,M,A_i=(int(x) for x in input().split())
A=0
for i in range(M):
    A+=A_i
if N<A:
    print("-1")

else:
    print(N-A)

### FIXED CODE ###

N,M=map(int,input().split())
A_i=list(map(int,input().split()))
A=0
for i in range(M):
    A+=A_i[i]
    
if N<A:
    print("-1")

else:
    print(N-A)
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M = map(int, input().split())
    s = [0] * M
    c = [0] * M
    for i in range(M):
        s[i], c[i] = map(int, input().split())

    for i in range(M):
        if s[i] == 1 and c[i] == 0 and N > 1:
            print(-1)
            exit()

    z = zip(s, c)
    z = sorted(z)
    s, c = zip(*z)
    s = list(s)
    c = list(c)

    for i in range(M - 1):
        if s[i] == s[i + 1]:
            if c[i] != c[i + 1]:
                print(-1)
                exit()

    for i in range(1, N + 1):
        if i not in s:
            s.append(i)
            if i == 1:
                c.append(1)
            else:
                c.append(0)

    z = zip(s, c)
    z = sorted(z)
    s, c = zip(*z)
    s = list(s)
    c = list(c)

    k = 1
    ans = ''
    for i in range(len(s)):
        if s[i] == k:
            ans += str(c[i])
            k += 1
    print(ans)




if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M = map(int, input().split())
    s = [0] * M
    c = [0] * M
    for i in range(M):
        s[i], c[i] = map(int, input().split())

    if M == 0:
        if N == 1:
            print(0)
            exit()
        elif N == 2:
            print(10)
            exit()
        elif N == 3:
            print(100)
            exit()

    for i in range(M):
        if s[i] == 1 and c[i] == 0 and N > 1:
            print(-1)
            exit()

    z = zip(s, c)
    z = sorted(z)
    s, c = zip(*z)
    s = list(s)
    c = list(c)

    for i in range(M - 1):
        if s[i] == s[i + 1]:
            if c[i] != c[i + 1]:
                print(-1)
                exit()

    for i in range(1, N + 1):
        if i not in s:
            s.append(i)
            if i == 1:
                c.append(1)
            else:
                c.append(0)

    z = zip(s, c)
    z = sorted(z)
    s, c = zip(*z)
    s = list(s)
    c = list(c)

    k = 1
    ans = ''
    for i in range(len(s)):
        if s[i] == k:
            ans += str(c[i])
            k += 1
    print(ans)




if __name__ == '__main__':
    main()
for i in range(10000):
    H,W=input().split())
    s = ""
    for j in range(int(W)):
        s = s + "#"
    for k in range(int(H)):
        print(s)
    print("")


### FIXED CODE ###

for i in range(10000):
    H,W=input().split()
    if H=="0" and W=="0":
        break
    s = ""
    for j in range(int(W)):
        s = s + "#"
    for k in range(int(H)):
        print(s)
    print("")
# -*- coding: utf-8 -*-
n, m = [int(x) for x in input().split()]
adj = [[0]*m for i in range(m)]
visited = [0]*m
for i in range(m):
    a, b = [int(x) for x in input().split()]
    adj[a-1][b-1] = 1
    adj[b-1][a-1] = 1

ans = 0
def dfs(v):
    global ans
    if sum(visited) == m:
        ans += 1
    for i in range(m):
        if adj[v-1][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i)
            visited[i] = 0

dfs(1)
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, m = [int(x) for x in input().split()]
adj = [[0]*n for i in range(n)]
visited = [0]*n
for i in range(m):
    a, b = [int(x) for x in input().split()]
    adj[a-1][b-1] = 1
    adj[b-1][a-1] = 1

ans = 0
def dfs(v):
    global ans
    if sum(visited) == n:
        ans += 1
    for i in range(n):
        if adj[v-1][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i+1)
            visited[i] = 0

visited[0] = 1
dfs(1)
print(ans)
n,k,c=[int(x) for x in input().split()]
s=list(input())

L=[]
R=[]
i=0
while i < n:
    
    if s[i]=="o":
        L.append(i)
        i+=2
    i+=1

i=0
while i < n:
    
    if s[n-i-1]=="o":
        R.append(n-i-1)
        i+=2
    i+=1
    


days=[]

for i in range(k):
    
    if L[i]==R[i]:
        days.append(L[i])

for i in range(len(days)):
    print(days[i])

### FIXED CODE ###

n,k,c=[int(x) for x in input().split()]
s=list(input())

L=[]
R=[]

i=0
while i < n:  
    if s[i]=="o":
        L.append(i)
        i+=c
    i+=1

i=0
while i < n:
    if s[n-i-1]=="o":
        R.append(n-i-1)
        i+=c
    i+=1
    
days=[]
for i in range(k):
    if L[i]==R[k-i-1]:
        days.append(L[i])


for i in range(len(days)):
    print(days[i]+1)
a=input("")
flag=False
for i in xrange(0,len(a)-2):
  if a[i]=='A' and a[i+1]=='C':
    flag=True
if flag==True:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a=input("");
flag=False;
for i in range(0,len(a)-1):
  if a[i]=='A' and a[i+1]=='C':
    flag=True;
if flag==True:
  print("Yes");
else:
  print("No");
N,Q = map(int,input().split())
S = str(input())
l,r = map(int,input().split())
count_list = []
for i in range(1,N-1):
    if S[i-1] == "A" and S[i] == "C":
        count_list.append(1)
    else:
        count_list.append(0)
    
for j in range(Q):
    sub_count = count_list[l[j]-1:r[j]-1]
    print(sum(sub_count))

### FIXED CODE ###

N,Q = map(int,input().split())
S = str(input())
l,r = [0]*Q,[0]*Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())
    
count_list = []
count = 0
count_list.append(0)
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        count += 1
        count_list.append(count)
    else:
        count_list.append(count)
    
for j in range(Q):
    print(count_list[r[j]-1]-count_list[l[j]-1])
n = int(input())
a = [[] for i in range(n)]

for i in range(n):
    v = list(map(int, input().split()))
    u = v[0] - 1
    for j in v[2:]:
        a[u].append(j-1)

d = [0] * n
isDiscovered = [False] * n

def bfs(x):
    global time_stamp
    time_stamp += 1
    for i in a[x]:
        if not isDiscovered[i]:
            isDiscovered [i] = True
            d[i] = d[x] + 1

bfs(0)
d_ = 1
isDiscovered [0] = True
while not(isDiscovered == [True] * n):
    for i in range(n):
        if d[i] is d_ :
            bfs(i)
    d_ += 1

for i in range(n):
    print(i+1, d[i])

### FIXED CODE ###

n = int(input())
a = [[] for i in range(n)]

for i in range(n):
    v = list(map(int, input().split()))
    u = v[0] - 1
    for j in v[2:]:
        a[u].append(j-1)

d = [-1] * n
isDiscovered = [False] * n

def bfs(x):
    for i in a[x]:
        if not isDiscovered[i]:
            isDiscovered [i] = True
            d[i] = d[x] + 1

d_ = 0
isDiscovered [0] = True
d[0] = 0
bfs(0)

flag = True
while flag:
    flag = False
    for i in range(n):
        if d[i] is d_ :
            flag = True
            bfs(i)
    d_ += 1

for i in range(n):
    print(i+1, d[i])
d=int(input())
if d=25:
  print('Christmas') 
elif d=24:
  print('Christmas Eve')
elif d=23:
  print('Christmas Eve Eve')
else :
  print('Christmas Eve Eve Eve')
 

### FIXED CODE ###

d=int(input())
if d==25:
  print('Christmas') 
elif d==24:
  print('Christmas Eve')
elif d==23:
  print('Christmas Eve Eve')
else :
  print('Christmas Eve Eve Eve')
lit=raw_input().lower()
Dic={'a':0,'b':0,'c':0,'d':0,'e':0,'f':0,'g':0,'h':0,'i':0,'j':0,'k':0,'l':0,'m':0,'n':0,'o':0,'p':0,'q':0,'r':0,'s':0,'t':0,'u':0,'v':0,'w':0,'x':0,'y':0,'z':0 }
for i in lit:
	Dic[i]+=1
Key=Dic.keys()
Key.sort()
for key in Key:
	print key, ":" ,Dic[key]

### FIXED CODE ###

import sys;
Dic={'a':0,'b':0,'c':0,'d':0,'e':0,'f':0,'g':0,'h':0,'i':0,'j':0,'k':0,'l':0,'m':0,'n':0,'o':0,'p':0,'q':0,'r':0,'s':0,'t':0,'u':0,'v':0,'w':0,'x':0,'y':0,'z':0 }
while True:
	lit=sys.stdin.readline().rstrip().lower()
	if not lit: break
	for i in lit:
		if ord('a')<=ord(i)<=ord('z'):
			Dic[i]+=1
Key=Dic.keys()
Key.sort()
for key in Key:
	print key, ":" ,Dic[key]
A, B, C, x = map(int, [input() for i in range(4)])
ans = [ _ for a in range(A+1) for b in range(B+1) for c in range(C+1) if a*500 + b*100+ c*50 == x ]
print(len(ans))

### FIXED CODE ###

s = []
for i in range(4):
    s.append(int(input()))

count = 0
for a in range(s[0] + 1):
    for b in range(s[1] + 1):
        for c in range(s[2] + 1):
            if( a*500 + b*100 + c*50 == s[3] ):
                count = count + 1

print(count)
n,a,b = map(int,input().split())
mod = 10**9+7
count = 0
def cmb(n,r):
  if n == 0 or n == r: return 1
  if r == 1: return n
  return cmb(n-1,r) + cmb (n-1,r-1)
for i in range(1,n+1):
  if i != a and i != b:
    count += cmb(n,i)
print(count % mod)

### FIXED CODE ###

def pow(a,b,c):
    ans = 1
    while b > 0:
        if b & 1:
            ans = ans*a % c
        a = a*a % c
        b = b >> 1
    return ans
def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(n-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num*pow(den,c-2,c) % c
mod = 10**9+7
n,a,b = map(int,input().split())
ans  = (pow(2,n,mod)-cmb(n,a,mod)-cmb(n,b,mod)-1) % mod
if ans < 0:
    ans = ans + mod
print(ans)
N = int(input())
A = []
for i in range(N):
	A.append(map(int, input().split()))

A.sort(reverse=True)
ans = 0

if N%2 == 1:
	for i in range((N+1)/2):
		ans += A[i]*2
	ans -= A[0]
	ans -= A[(N+1)/2]
	print(ans)
else:
	for i in range(N/2):
		ans += A[i]*2
	ans -= A[0]
	print(ans)

### FIXED CODE ###

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

A.sort(reverse=True)
ans = 0

for i in range(N-1):
	ans += A[(i+1)//2]

print(ans)
N = input()
dL = [0]*N
for n in range(N):
  dL[n] = int(input())
print(len(list(set(dL))))

### FIXED CODE ###

N = int(input())
dL = [0]*N
for n in range(N):
  dL[n] = int(input())
print(len(list(set(dL))))
#入力
n,m = map(int, input().split())
sc=[list(map(int,input().split())) for i in range(m)]
#桁、数字の格納所
s=[]
c=[]
#flag
f=0
#n個の0が並ぶ数列
ans=[str(0) for i in range(n)]
#桁数字の格納
for i in range(m):
    if sc[i][0]==1 and sc[i][1]==0 and n!=1:#1桁目に0が入る2桁以上の数の時
        f=-1#ERROR
        break
    else:
        if sc[i][0] in s:#ある桁がすでに入力されている時
            if sc[i][1]!=c[s.index(sc[i][0])]:#その桁の数字が異なる場合ERROR
                f=-1
                break
        else:#ある桁がまだ入力されていない時
            ans[sc[i][0]-1]=str(sc[i][1])#ある桁に数字を入力(文字列として)
            s.append(sc[i][0])
            c.append(sc[i][1])

if f==-1:
    print(-1)
else:#flagが正常
    if n==1:
        print(c[0])
    else:
        if ans[0]==str(0):
            ans[0]==str(1)
        print(''.join(ans))


### FIXED CODE ###

N,M=map(int,input().split())
sc = [list(map(int, input().split())) for _ in range(M)]
a=str(0)*N
A=[a[i] for i in range(len(a))]
x=0
#print(sc)
b=[]
c=[]
for i in range(M):
    if (sc[i][0] == 1) and (sc[i][1]==0) and (N!=1):
        x=-1
        break
    else:
        if (sc[i][0]) in b:#左から何桁目の情報が既にある場合、既に登録されているその桁の値と新たに登録しようとしてるその桁の値が異なるとき弾く
            if sc[i][1]!=int(c[b.index(sc[i][0])]):
                #print(c[b.index(sc[i][0])])
                x=-1
                break
        else:
            A[sc[i][0]-1]=str(sc[i][1])
            b.append(sc[i][0])
            c.append(sc[i][1])
if x==-1:
    print(-1)      
elif b==[] and (N!=1):
    if N==2:
        print(10)
    elif N==3:
        print(100)
elif (1 not in b) and(N!=1):
    A[0]=str(1)
    a="".join(A)
    print(a)
elif  (1 not in b) and (2 not in b) and (N==3):
    A[0]=str(1)
    A[1]=str(0)
    a="".join(A)
    print(a)

else:
    a="".join(A)
    print(a)
from collections import deque
h,w=list(map(int, input().split()))
s = [input() for _ in range(h)]

water=[[0]*w for _ in range(w)]
water[0][0]=1
a_index=[]
a_column=[]
a_index.append(0)
a_column.append(0)
b=[]
count=0
flag=True
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            water[i][j]=3000
            count+=1
while water[h-1][w-1]==0:
    for i,j in zip(a_index,a_column):
        if water[i][j]==1:
            if i>0:
                if water[i-1][j]==0:
                    water[i-1][j]+=1
                    b.insert(0,[i-1,j])
            if i<h-1:
                if water[i+1][j]==0:
                    water[i+1][j]+=1
                    b.insert(0,[i+1,j])
            if j>0:
                if water[i][j-1]==0:
                    water[i][j-1]+=1
                    b.insert(0,[i,j-1])
            if j<w-1:
                if water[i][j+1]==0:
                    water[i][j+1]+=1
                    b.insert(0,[i,j+1])
        water[i][j]+=1
    a_index+=[x[0] for x in b]
    a_column+=[x[1] for x in b]

    if not b:
        flag=False
        break
    b=[]

if flag:
    print(h*w-water[0][0]-count)
else:
    print(-1)


### FIXED CODE ###

from collections import deque
h,w=list(map(int, input().split()))
s = [input() for _ in range(h)]

water=[[0]*w for _ in range(h)]
water[0][0]=1
a_index=[]
a_column=[]
a_index.append(0)
a_column.append(0)
b=[]
count=0

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            water[i][j]=3000
            count+=1
while water[h-1][w-1]==0:
    for i,j in zip(a_index,a_column):
        if water[i][j]==1:
            if i>0:
                if water[i-1][j]==0:
                    water[i-1][j]+=1
                    b.insert(0,[i-1,j])
            if i<h-1:
                if water[i+1][j]==0:
                    water[i+1][j]+=1
                    b.insert(0,[i+1,j])
            if j>0:
                if water[i][j-1]==0:
                    water[i][j-1]+=1
                    b.insert(0,[i,j-1])
            if j<w-1:
                if water[i][j+1]==0:
                    water[i][j+1]+=1
                    b.insert(0,[i,j+1])
        water[i][j]+=1

    a_index+=[x[0] for x in b]
    a_column+=[x[1] for x in b]

    if not b:
        print(-1)
        exit()
    b=[]

print(h*w-water[0][0]-count)
def Even(x):
  return  2 * x

def Odd(x):
  return 2 * x - 1

N, M = map(int, input().split())
G = list(map(Even, range(1, N+1)))#偶数
K = list(map(Odd, range(1, M+1)))#奇数

even=list()

for n in range(0, N):
  for nm in range(n+1, N):
    even.append(G[n]+G[nm])
  
for m in range(0, M):
  for mm in range(m+1, M):
    if int(G[n])+int(K[m]) %2 ==0:
      even.append(K[m]+K[mm])
print(len(even))

### FIXED CODE ###

def Even(x):
  return  2 * x

def Odd(x):
  return 2 * x - 1

N, M = map(int, input().split())
G = list(map(Even, range(1, N+1)))#偶数
K = list(map(Odd, range(1, M+1)))#奇数

even=list()

for n in range(0, N):
  for nm in range(n+1, N):
    even.append(G[n]+G[nm])
  
for m in range(0, M):
  for mm in range(m+1, M):
    even.append(K[m]+K[mm])

print(len(even))
h,w,K = map(int,input().split())
cum = [[0 for _ in range(w+1)]]
for _ in range(h):
  tmp = input()
  add = [0]
  for j in range(w):
    add.append(add[-1]+int(tmp[j]))
  cum.append(add)
for i in range(h):
  for j in range(w):
    cum[i+1][j+1] += cum[i][j+1]
time = [0 for _ in range(h-1)]
def nex(time):
  for d in range(h-1):
    if time[d] == 0:
      time[d] = 1
      return time
    else:
      time[d] = 0
  else:
    return 'over'
can = []
while time != 'over':
  tmp = [0]
  for d in range(h-1):
    if time[d] == 1:
      tmp.append(d+1)
  tmp.append(h)
  #print(tmp,time)
  l = len(tmp) - 1
  ans = l - 1
  now = 0
  att = 1
  for j in range(1,w+1):
    cand = []
    for k in range(l):
      cand.append(cum[tmp[k+1]][j] - cum[tmp[k+1]][now] - cum[tmp[k]][j] + cum[tmp[k]][now])
    #print(cand,now,tmp)
    if max(cand) > K:
      if att == 1:
        break
      now = j - 1
      ans += 1
      att = 1
    else:
      att = 0
  else:
    #print(l-1,ans,time)
    can.append(ans)
  time = nex(time)
  #print(tmp,l-1,ans)
print(min(can))

### FIXED CODE ###

h,w,K = map(int,input().split())
cum = [[0 for _ in range(w+1)]]
for _ in range(h):
  tmp = input()
  add = [0]
  for j in range(w):
    add.append(add[-1]+int(tmp[j]))
  cum.append(add)
for i in range(h):
  for j in range(w):
    cum[i+1][j+1] += cum[i][j+1]
time = [0 for _ in range(h-1)]
def nex(time):
  for d in range(h-1):
    if time[d] == 0:
      time[d] = 1
      return time
    else:
      time[d] = 0
  else:
    return 'over'
can = []
while time != 'over':
  tmp = [0]
  for d in range(h-1):
    if time[d] == 1:
      tmp.append(d+1)
  tmp.append(h)
  #print(tmp,time)
  l = len(tmp) - 1
  ans = l - 1
  now = 0
  att = 1
  for j in range(1,w+1):
    cand = []
    for k in range(l):
      cand.append(cum[tmp[k+1]][j] - cum[tmp[k+1]][now] - cum[tmp[k]][j] + cum[tmp[k]][now])
    #print(cand,now,tmp)
    if max(cand) > K:
      now = j - 1
      ans += 1
      cane = []
      for k in range(l):
        cane.append(cum[tmp[k+1]][j] - cum[tmp[k+1]][now] - cum[tmp[k]][j] + cum[tmp[k]][now])
        #if tmp == [0,1,3]:
          #print(cane,j)
        if max(cane) > K:
          ans += 1
          now = j
    #print(l-1,ans,time)
  else:
    can.append(ans)
  time = nex(time)
  #print(tmp,l-1,ans)
print(min(can))
import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    K= c+d+5
    fac = [0 for _ in range(K+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,K+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(e,f):
        return (fac[e+f]*pow(fac[e],MOD-2,MOD)*pow(fac[f],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if _name_ == "_main_":
    main()
#print the result

### FIXED CODE ###

import sys
import math
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if __name__ == "__main__":
    main()
N = int(raw_input())
line = raw_input().split(' ')
M = int(raw_input())
for i in range(M):
    x = map(int,raw_input().split(' ')
    print sum(line)-(line[x[0]]-x[1])

### FIXED CODE ###

N = int(raw_input())
line = map(int,raw_input().split(' '))
M = int(raw_input())
for i in range(M):
    x = map(int,raw_input().split(' '))
    s = sum(line)-(line[x[0]-1]-x[1])
    print s
s = input()

tmp = ""
for val in s:
  if tmp == val:
    print("Bad")
    import sys.exit(0)
  tmp = val

print("Good")

### FIXED CODE ###

s = input()
 
tmp = ""
for val in s:
  if tmp == val:
    print("Bad")
    import sys
    sys.exit(0)
  tmp = val
 
print("Good")
S = input()
T = input()
X = len(T) - 1

if S in T and (len(X) == len(S)):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

S = input()
T = input()
X = int(len(T)) - 1
Y = T[:-1]

if S == Y and X == int(len(S)):
    print('Yes')
else:
    print('No')
def main(a):
    for ind,_ in enumerate(a):
        #print(inds[ind::ind+1])
        buf = a[ind::ind+1]
        if (buf[0]==0 and sum(buf)%2==0) or (buf[0]==1 and sum(buf)%2==1):
            pass
        else:
            print(-1)
            return 0

    print(sum(a))
    if sum(a)>0:print(' '.join([str(ind+1) for ind,x in enumerate(a) if x == 1]))

N = int(input())
a = [int(input()) for _ in range(N)]
    
main(a)


### FIXED CODE ###

def main(A,N):
    A = [0] + A
    for a in range(N//2,0,-1):
        #print(inds[ind::ind+1])
        if sum(A[a::a]) %2== 0:
            A[a] = 0
        else:
            A[a] = 1
        
    res = [x for x in range(0,N+1) if A[x]]
    print(len(res))
    print(*res)

N = int(input())
A = [int(x) for x in input().split()]
    
main(A,N)
N = int(input())
NUM = 1000000007
A = [int(input()) for _ in range(N)]
MASS = 0
for i in range (N):
    I = A[i] % NUM
    I = (I * (N - 1)) % NUM
    MASS += I
print(MASS % NUM)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
total = 0
sub = 0
for i in a:
    total += i
    sub += i * i
print((((total * total) - sub) // 2) % (10 ** 9 + 7))