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

def mpw(n,m):
    ret=1
    while m>0:
        if m&1:
            ret*=n
            ret%=M
        n*=n
        n%=M;
        m>>=1
    return ret;
def pw(n,m):
    ret=1
    while m>0:
        if m&1:
            ret*=n
        n*=n
        m>>=1
    return ret;

L,A,B,M=map(int,input().split())
ans=0
d=0
for k in range(18,0,-1):
#    l=max((10**(k-1)-A+B-1)//B,0)
    l=max((pw(10,(k-1))-A+B-1)//B,0)
#    r=min((10**k-A-1)//B,L-1)
    r=min((pw(10,k)-A-1)//B,L-1)
    if l<=r:
        ans+=mpw(10,d)*(B*pw(10,k)*(pw(10,(r-l)*k)-1)//(pw(10,k)-1)+(A+B*l)*pw(10,(r-l+1)*k)-(A+B*r))//(pw(10,k)-1)
#        ans+=mpw(10,d)*((B*10**k*(10**((r-l)*k)-1)//(10**k-1)+(A+B*l)*10**((r-l+1)*k))-(A+B*r))//(10**k-1)
        ans%=M
        d+=(r-l+1)*k
#    print(k,l,r)
print(ans)


### FIXED CODE ###

def mpw(n,m):
    ret=1
    while m>0:
        if m&1:
            ret*=n
            ret%=M
        n*=n
        n%=M;
        m>>=1
    return ret;
def pw(n,m):
    ret=1
    while m>0:
        if m&1:
            ret*=n
        n*=n
        m>>=1
    return ret;
def delta(i,j):
    if i==j:
        return 1
    return 0
def mtxmpw(A,m):
    ret=[[delta(i,j) for i in range(len(A))] for j in range(len(A))]
    while m>0:
        if m&1:
            ret=mul(ret,A)
        A=mul(A,A)
        m>>=1
    return ret
def mul(A,B):
    ret=[[0 for i in range(len(B[0]))] for j in range(len(A))]
    for i in range(len(A)):
        for j in range(len(B[0])):
            for k in range(len(B)):
                ret[i][j]+=A[i][k]*B[k][j]
                ret[i][j]%=M
    return ret

L,A,B,M=map(int,input().split())
ans=0
d=0
for k in range(18,0,-1):
    l=max((pw(10,(k-1))-A+B-1)//B,0)
    r=min((pw(10,k)-A-1)//B,L-1)
    if l<=r:
        MT=[[1,mpw(10,k),0],[0,mpw(10,k),(M-B*mpw(10,k)%M)%M],[0,0,mpw(10,k)]]
        v=[[(A+B*r)%M],[(A+B*(r-1)%M+M)%M],[1]]
        u=mul(mtxmpw(MT,r-l),v)
        ans+=mpw(10,d)*u[0][0]%M;
        ans%=M;
        d+=(r-l+1)*k
print(ans)
### BUGGY CODE ###

# from collections import deque
from collections import Counter
from scipy.misc import comb
from copy import deepcopy

n = int(input())
a = list(map(int, input().split()))
cnt_n = 0
a_n = deepcopy(a)
c = Counter(a_n)
for key in c:
    cnt_n += comb(c[key], 2, exact=True)

for k in range(len(a)):
    a_n = deepcopy(a)
    a_k = deepcopy(a[k])
    a_n.pop(k)
    cnt_k = a_n.count(a_k)
    print(cnt_n - cnt_k)


### FIXED CODE ###

# from collections import deque
from collections import Counter
from scipy.misc import comb
# from copy import deepcopy

n = int(input())
a = list(map(int, input().split()))
C = Counter(a)
S = 0
for key in C:
    S += comb(C[key], 2, exact=True)

for k in range(n):
    A = a[k]
    print(S - C[A] + 1)
### BUGGY CODE ###

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

a = []
for _ in range(M):
    a.append(int(input()))

val = [0,1]
for i in range(1, N + 1):
    ans = val[-2] + val[-1]
    val.append(ans)
    if len(a) > 0:
        if i == a[0]:
            val[-1] = 0
            a.pop(0)

print(ans % (10**9 +7))

### FIXED CODE ###

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

a = []
for _ in range(M):
    a.append(int(input()))

val = [0,1]
for i in range(1, N + 1):
    ans = val[-2] + val[-1]
    val.append(ans)
    if len(a) > 0:
        if i == a[0]:
            val[-1] = 0
            a.pop(0)

print(ans % (10**9 +7))
### BUGGY CODE ###


def canProd(i,m,a,n):
    
    if m == 0:
        return True
    if i >= n:
        return False

    res = canProd(i+1,m,a,n) or canProd(i+1,m-a[i],a,n)
    return res


n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

tf = []

for i in range(1,2001):
    if canProd(0,i,a,n):
        tf.append(i)



for i in m:
    if i in tf:
        print("yes")
    else:
        print("no")

### FIXED CODE ###

from functools import lru_cache

@lru_cache(maxsize = None)
def canProd(i,m):
     
    if m == 0:
        return True
    if i >= n:
        return False
 
    res = canProd(i+1,m) or canProd(i+1,m-a[i])
    return res
 
 
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

rs = [None]*2001

maxm = max(m)
minm = min(m)

for i in range(minm,maxm+1):
    if canProd(0,i):
        rs[i] = "yes"
    else:
        rs[i] = "no"

for i in m:
    print(rs[i])
### BUGGY CODE ###

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

for _ in range(M):
  b, c = map(int, input().split())
  A += [c]*b

A.sort(reverse=True)
print(sum(A[:N]))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
from operator import itemgetter
BC.sort(key=itemgetter(1), reverse=True)

for b, c in BC:
  A += [c]*b
  if len(A) > 2*N:
    break

A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

from functools import reduce
from operator import mul

N=int(input())

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

result=reduce(mul,A)

if result>10**18:
    print(-1)
else:
    print(result)



### FIXED CODE ###

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

if 0 in A:
    print(0)
else:
    result=1
    for a in A:
        result=result*a
        if result>10**18:
            result=-1
            break
    print(result)
### BUGGY CODE ###

import collections

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while len(q)!=0:
  x,y=q.popleft()
  c=cost[y][x]
  for i in range(4):
    for j in range(1,k+1):
      if x+j*dx[i]<0 or w<=x+j*dx[i] or y+j*dy[i]<0 or h<=y+j*dy[i]:
        break
      if board[y+j*dy[i]][x+j*dx[i]]=='@':
        break
      if cost[y+j*dy[i]][x+j*dx[i]]<=c:
        break
      q.append((x+j*dx[i],y+j*dy[i]))
      cost[y+j*dy[i]][x+j*dx[i]]=c+1
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])

### FIXED CODE ###

import collections

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while len(q)!=0:
  x,y=q.popleft()
  c=cost[y][x]
  for i in range(4):
    for j in range(1,k+1):
      if x+j*dx[i]<0 or w<=x+j*dx[i] or y+j*dy[i]<0 or h<=y+j*dy[i]:
        break
      if board[y+j*dy[i]][x+j*dx[i]]=='@':
        break
      if cost[y+j*dy[i]][x+j*dx[i]]<=c:
        break
      if cost[y+j*dy[i]][x+j*dx[i]]>c+1:
        q.append((x+j*dx[i],y+j*dy[i]))
        cost[y+j*dy[i]][x+j*dx[i]]=c+1
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N = int(input())
MOD = 10**9 + 7
tree = [[] for i in range(N+1)]
for i in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b)
  tree[b].append(a)

# 頂点1をルートにして各頂点より下にある部分木の頂点数を求めていく
root, par = 1, 0
sizes = [0] * (N+1)
order = [[root, par]]
def calc_nums(node, par):
  global sizes
  global order
  if sizes[node] > 0:
    return sizes[node]
  children = tree[node]
  res = 1
  for child in children:
    if child == par:
      continue
    order.append([child, node])
    res += calc_nums(child, node)
  sizes[node] = res
  return res

calc_nums(root, par)

# 2の累乗を事前に計算しておく
prod2 = [1]
for i in range(N):
  prod2.append(prod2[-1] * 2 % MOD)

# 各頂点について、その頂点が穴あき度としてカウントされる状況を独立に計算する
demo = 0 # 分子
div = prod2[N] # 分母
base = prod2[N-1] - 1
for node, par in order:
  children = tree[node]
  num = base
  num_par = N - 1
  for child in children:
    if child == par:
      continue
    s = sizes[child]
    num_par -= s
    num -= prod2[s] - 1 
  num -= prod2[num_par] - 1
  demo += num
    
ans = demo * pow(div, MOD-2, MOD) % MOD
print(ans)

### FIXED CODE ###

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

N = int(input())
MOD = 10**9 + 7
tree = [[] for i in range(N+1)]
for i in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b)
  tree[b].append(a)

# 頂点1をルートにして各頂点より下にある部分木の頂点数を求めていく
root, par = 1, 0
sizes = [0] * (N+1)
order = [[root, par]]
def calc_nums(node, par):
  global sizes
  global order
  if sizes[node] > 0:
    return sizes[node]
  children = tree[node]
  res = 1
  for child in children:
    if child == par:
      continue
    order.append([child, node])
    res += calc_nums(child, node)
  sizes[node] = res
  return res

_ = calc_nums(root, par)

# 2の累乗を事前に計算しておく
prod2 = [1]
for i in range(N):
  prod2.append(prod2[-1] * 2 % MOD)

# 各頂点について、その頂点が穴あき度としてカウントされる状況を独立に計算する
demo = 0 # 分子
div = prod2[N] # 分母
base = prod2[N-1] - 1
for node, par in order:
  children = tree[node]
  num = base
  num_par = N - 1
  for child in children:
    if child == par:
      continue
    s = sizes[child]
    num_par -= s
    num -= prod2[s] - 1 
  num -= prod2[num_par] - 1
  demo += num
    
ans = demo * pow(div, MOD-2, MOD) % MOD
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
import heapq
a=list(map(int,input().split()))
heapq.heapify(a)

for _ in range(m):
    b,c=map(int,input().split())
    for i in range(b):
        x=heapq.heappop(a)
        if x<c:
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,x)
            break
print(sum(a))


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
l=[]
for i in range(n):
    l.append([1,a[i]])
for i in range(m):
    l.append(list(map(int,input().split())))
l.sort(key=lambda x:x[1], reverse=True)
c=0
ans=0
for i in range(n+m):
    ans+=l[i][1]*l[i][0]
    c+=l[i][0]
    if c>n:
        ans-=l[i][1]*(c-n)
        break
print(ans)
### BUGGY CODE ###

N , M = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(M)]
ans = "IMPOSSIBLE"
for n in range(1,N):
  if ([1,n] in s) and ([n,N] in s):
    ans = "POSSIBLE"
print(ans)

### FIXED CODE ###

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

ans = "IMPOSSIBLE"

start_candidate = [X[1] for X in s if X[0]==1 ]
goal_candidate = [X[0] for X in s if X[1]==N]

ans = len(start_candidate)+len(goal_candidate)-len(set(start_candidate+goal_candidate))
if ans != 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

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

cum_r = [0] * (N + 1)  # cum_r[i] = i文字目までに含まれるRの数（i = 0, .., N)
cum_g = [0] * (N + 1)
cum_b = [0] * (N + 1)

for i in range(1, N + 1):
    cum_r[i] = cum_r[i - 1] + int(S[i - 1] == 'R')
    cum_g[i] = cum_g[i - 1] + int(S[i - 1] == 'G')
    cum_b[i] = cum_b[i - 1] + int(S[i - 1] == 'B')


dp = [0] * (N + 1)
for i in range(3, N + 1):
    dp[i] = dp[i - 1]
    for j in range(1, i - 1):
        if S[i - 1 - j] == S[i - 1]: continue

        if S[i - 1] == 'R':
            if S[i - 1 - j] == 'G':
                dp[i] += cum_b[i - 1 - j]
                if i - 1 - 2 * j >= 0 and S[i - 1 - 2 * j] == 'B':
                    dp[i] -= 1
            else: # B
                dp[i] += cum_g[i - 1 - j]
                if i - 1 - 2 * j >= 0 and S[i - 1 - 2 * j] == 'G':
                    dp[i] -= 1

        elif S[i - 1] == 'G':
            if S[i - 1 - j] == 'R':
                dp[i] += cum_b[i - 1 - j]
                if i - 1 - 2 * j >= 0 and S[i - 1 - 2 * j] == 'B':
                    dp[i] -= 1
            else: # B
                dp[i] += cum_r[i - 1 - j]
                if i - 1 - 2 * j >= 0 and S[i - 1 - 2 * j] == 'R':
                    dp[i] -= 1
        else:  # B
            if S[i - 1 - j] == 'R':
                dp[i] += cum_g[i - 1 - j]
                if i - 1 - 2 * j >= 0 and S[i - 1 - 2 * j] == 'G':
                    dp[i] -= 1
            else: # G
                dp[i] += cum_r[i - 1 - j]
                if i - 1 - 2 * j >= 0 and S[i - 1 - 2 * j] == 'R':
                    dp[i] -= 1
print(dp[N])


### FIXED CODE ###

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

sub = 0
for j in range(1, (N - 1) // 2 + 1):
    for i in range(0, N - 2 * j):
        if S[i] != S[i + j] and S[i + j] != S[i + 2 * j] and S[i + 2 * j] != S[i]:
            sub += 1

r = S.count('R')
g = S.count('G')
b = N - r - g

ans = r * g * b - sub
print(ans)
### BUGGY CODE ###

A, B, C, D, E, F = map(int, input().split())

#memo
list = [0, 0]

#操作1-4
ope1 = 100 * A
ope2 = 100 * B
ope3 = C
ope4 = D

#入れた水、砂糖の総量
w_sum = 0
s_sum = 0
#パーセンテージ
p = 0
#トータル
total = w_sum + s_sum
#砂糖の表示用の変数
s = 0

for i in range(101):
    for j in range(101):
        for k in range(31):
            for l in range(31):
                w_sum = l * ope1 + k * ope2
                s_sum = j * ope3 + i * ope4
                if w_sum != 0:
                    p_tmp = (s_sum / (w_sum + s_sum)) * 100
                    if w_sum + s_sum <= F and s_sum <= E * (l + k) :
                        if p_tmp >= p:
                            p = p_tmp
                            list[0] = w_sum + s_sum
                            list[1] = s_sum

print(list[0], list[1])                        


### FIXED CODE ###

def solve():
    
    A, B, C, D, E, F = map(int, input().split())
    memo = {}
    
    for a in range(31):
        for b in range(31):
            for c in range(101):
                for d in range(101):
                    w = (100*A)*a + (100*B)*b
                    s = C*c + D*d
                    if w ==0:
                        break
                    if w+s > F:
                        break
                    else:
                        if w/100 * E >= s:
                            density = 100*s/(w+s)
                            memo[a,b,c,d] = density
    
    max_v = max(memo.values())
    
    for k, v in memo.items():
        if v == max_v:
            print((100*A)*k[0] + (100*B)*k[1] + C*k[2] + D*k[3], C*k[2] + D*k[3] )
            break
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

L, R = map(int, input().split())
mod = 2019

for i in range(L, R) :
	for j in range(i + 1, R + 1) :
		if((i * j) % 2019 < mod) :
			mod = (i * j) % 2019
			x = ((i * j) // 2019) * 2019 + 2019
			if(x > i * R) :
				break
			else :
				pass
		else :
			pass
	if(mod == 0) :
		break
	else :
		pass
	
print(mod)

### FIXED CODE ###

L, R = map(int, input().split())
mod = 2019

for i in range(L, R) :
	for j in range(i + 1, R + 1) :
		if((i * j) % 2019 < mod) :
			mod = (i * j) % 2019
			x = ((i * j) // 2019) * 2019 + 2019
			if(x > i * R) :
				break
			else :
				pass
		elif(mod == 0) :
			break
		else :
			pass
	if(mod == 0) :
		break
	else :
		pass
	
print(mod)
### BUGGY CODE ###


"""
Writer: SPD_9X2
https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_e
Mの時、 a1<=a2<=a3…aN
を満たす通り数 X[M] が分かれば解ける(全ての順N!は等しいため)

当然、次のMにはa1から順に更新していくことになる(M+?にね)
Dの時
X[M] = (X[M-1] + X[M-2] +　… + X[M-D]) * N
が成立かな
X[0] = 1

N=2
X[0]=1
X[1]=2
X[2]=6

N=3
X[0]=1
X[1]=9

X[M]の更新式
→これが間違ってそう
X[M] = (X[M-1] + X[M-2] +　… + X[M-D]) * (1!+2!+3!+…N!)
→エスパーだけどなんか正しそう

X[H-1]を求めてN!を掛ければそれが答え
→サンプル合った！！
"""
import math
N,H,D = map(int,input().split())
mod = 10**9+7

mul = 0
fac = 1
for i in range(1,N+1):
    fac *= i
    fac %= mod
    mul += fac
    mul %= mod

X = [1]
nsum = 1
for i in range(H-1):

    #print (i,nsum,mul)
    X.append(nsum*mul%mod)

    nsum += X[-1]
    if i >= D-1:
        nsum -= X[i-D+1]
        

#print (X)
print (nsum * math.factorial(N) % mod)


### FIXED CODE ###


"""
Writer: SPD_9X2
https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_e
Mの時、 a1<=a2<=a3…aN
を満たす通り数 X[M] が分かれば解ける(全ての順N!は等しいため)

当然、次のMにはa1から順に更新していくことになる(M+?にね)
Dの時
X[M] = (X[M-1] + X[M-2] +　… + X[M-D]) * N
が成立かな
X[0] = 1

N=2
X[0]=1
X[1]=2
X[2]=6

N=3
X[0]=1
X[1]=9

X[M]の更新式
→これが間違ってそう
X[M] = (X[M-1] + X[M-2] +　… + X[M-D]) * (1!+2!+3!+…N!)
→エスパーだけどなんか正しそう

X[H-1]を求めてN!を掛ければそれが答え
→サンプル合った！！
"""
import math
N,H,D = map(int,input().split())
mod = 10**9+7

mul = 0
fac = 1
for i in range(1,N+1):
    fac *= i
    fac %= mod
    mul += fac
    mul %= mod

X = [1]
nsum = 1
for i in range(H-1):

    #print (i,nsum,mul)
    X.append(nsum*mul%mod)

    nsum += X[-1]
    nsum %= mod
    if i >= D-1:
        nsum -= X[i-D+1]
        

#print (X)
print (nsum * fac % mod)
### BUGGY CODE ###

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

for i in range(N):
    ans = 0
    AA = copy.copy(A)
    AA.pop(i)
    AAA = collections.Counter(AA)
    for j in AAA.values():
        if j>=2:
            ans += int(j*(j-1)/2)
    print(ans)

### FIXED CODE ###

import collections
import copy
N = int(input())
A = list(map(int,input().split()))
AA = collections.Counter(A)
ans = sum([i*(i-1)//2 for i in AA.values()])

for i in range(N):
    num = ans
    num -= AA[A[i]]-1
    print(num)
### BUGGY CODE ###

def resolve(SL):
    # L[0]!=0を起点とする
    cnt = 0
    for i in range(len(SL)-1):
        s0 = SL[i]
        s1 = SL[i+1]
        if(s0>0 and s1>=0):
            SL[(i+1):] = [s-(s1+1) for s in SL[(i+1):]]
            cnt += (s1+1)
        elif(s0<0 and s1<=0):
            SL[(i+1):] = [s+(-s1+1) for s in SL[(i+1):]]
            cnt += (-s1+1)  
    return cnt
            
    
def ans(L):
    SL = [sum(L[:(i+1)]) for i in range(len(L))]
    c0,c1=0,0
    
    if (L[0]>0):
        c0 = resolve(SL)
        c1 = (L[0]+1) + resolve(list(map(lambda x:x-(L[0]+1), SL)))
    elif (L[0]<0):
        c0 = resolve(SL)
        c1 = (-L[0]+1) + resolve(list(map(lambda x:x+(-L[0]+1), SL)))
    else:
        c0 = 1 + resolve(list(map(lambda x:x+1, SL)))
        c1 = 1 + resolve(list(map(lambda x:x-1, SL)))
    
    return(min(c0,c1))
  
N = int(input())
L = [int(x) for x in input().split(' ')]
 
print(ans(L))

### FIXED CODE ###

import copy 

def resolve(List):
    # L[0]!=0を起点とする
    L = copy.deepcopy(List)
    cnt = 0
    s = L[0]
    for i in range(1,len(L)):
        a = L[i]
        if(s>0 and s+a>=0):
            L[i] = -s-1
            cnt += (s+a+1)
            s = -1
        elif(s<0 and s+a<=0):
            L[i] = -s+1
            cnt += (-s-a+1)
            s = 1
        else:
            s += a
    return cnt      

def ans(List):
    L = copy.deepcopy(List)
    a = L[0]
    c0,c1=0,0

    if (a>0):
        c0 = resolve(L)
        c1 = (a+1) + resolve([-1]+L[1:])
    elif (a<0):
        c0 = resolve(L)
        c1 = (-a+1) + resolve([1]+L[1:])
    else:
        c0 = 1 + resolve([1]+L[1:])
        c1 = 1 + resolve([-1]+L[1:])
    
    return(min(c0,c1))

def main():
    N = int(input())
    List = [int(x) for x in input().split(' ')]
    print(ans(List))

main()
### BUGGY CODE ###

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

li = []
while len(li) <= n:
  for i in range(a):
    li.append('b')
  for i in range(b):
    li.append('a')

ans = li[:n].count('b')

print(ans)

### FIXED CODE ###

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

if n % (a + b) <= a:
  ans = n//(a + b) * a + n % (a + b)
else:
  ans = n//(a + b) * a + a

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

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

dp = [0] * (N+1)
for a, b in ((a, b) for a, b in zip(A, B) if a < b):
    for w in range(1, N+1):
        if w-a >= 0:
            dp[w] = max(dp[w], dp[w-a] + b-a)

M = max(dp) + N
dp = [0] * (M+1)
for a, b in ((a, b) for a, b in zip(A, B) if a > b):
    for w in range(1, M+1):
        if w-b >= 0:
            dp[w] = max(dp[w], dp[w-b] + a-b)

print(max(dp) + M)


### FIXED CODE ###

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

dp = [0] * (N+1)
for a, b in ((a, b) for a, b in zip(A, B) if a < b):
    for w in range(a, N+1):
        dp[w] = max(dp[w], dp[w-a] + b-a)

M = max(dp) + N
dp = [0] * (M+1)
for a, b in ((a, b) for a, b in zip(A, B) if a > b):
    for w in range(b, M+1):
        dp[w] = max(dp[w], dp[w-b] + a-b)

print(max(dp) + M)
### BUGGY CODE ###

# B - Frog 2
import sys
sys.setrecursionlimit(10**6)

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

# 無限大の値
INF = 10**10

# DP テーブル
dp = [0]*(100010)

# DP テーブル全体を初期化
for i in range(100010):
    dp[i] = INF 

# 初期条件
def rec(v):
    # DP の値が既に更新されていたらそのままリターン 
    if dp[v] < INF:
        return dp[v]
    if v == 0:
        dp[0] = 0
        return 0
    
    res = INF
    for k in range(1,K+1):
        # 遷移元の足場がないとき

        if v-k < 0:
            continue
        # 足場 v-k から足場 v に移動する
        res = min(res, rec(v-k) + abs(h[v]-h[v-k]))
        # 結果をメモして返す
        dp[v] = res
    return res
print(rec(N-1))

### FIXED CODE ###

# B - Frog 2
N,K = map(int,input().split())
h = list(map(int,input().split()))

# 無限大の値
INF = 10**10

# DP テーブル
dp = [0]*(100010)

# DP テーブル全体を初期化
for i in range(100010):
    dp[i] = INF 

# 初期条件
dp[0] = 0

for v in range(1,N):
    for k in range(1,K+1):
        # 遷移元の足場がないとき
        if v-k < 0:
            continue
        # 足場 v-k から足場 v に移動する
        dp[v] = min(dp[v], dp[v-k] + abs(h[v]-h[v-k]))
print(dp[N-1])
### BUGGY CODE ###

def myAnswer(N:int,M:int,X:list,Y:list) -> int:
   red = 0
   ans = {0}
   box = [1] * N
   for x,y in zip(X,Y):
      if(x-1 in ans):
         ans.add(y-1)
      box[x-1] -= 1
      box[y-1] += 1
      for i in list(ans):
         if(box[i] == 0):
            ans.remove(i)
   return len(ans)

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   X = []
   Y = []
   for _ in range(M):
      x,y=map(int,input().split())
      X.append(x)
      Y.append(y)
   print(myAnswer(N,M,X,Y))
if __name__ == '__main__':
   main()

### FIXED CODE ###

'''
Accepted    　:No
difficult   　: 
ペナルティ　  　:5分
実際の回答時間  :分
WAの回数　     :回
合計時間　　  　:分
'''

def myAnswer(N:int,M:int,X:list,Y:list) -> int:
   ans = {0}
   box = [1] * N
   for x,y in zip(X,Y):
      if(x-1 in ans):
         if(box[x - 1]==1):
            ans.remove(x-1)
         ans.add(y-1)
      box[x-1] -= 1
      box[y-1] += 1
   return len(ans)

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   X = []
   Y = []
   for _ in range(M):
      x,y=map(int,input().split())
      X.append(x)
      Y.append(y)
   print(myAnswer(N,M,X,Y))
if __name__ == '__main__':
   main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def l(): return [int(a) for a in input().split(" ")] 
ka = l()
lis = {}
saku = []
for i,a in zip(range(ka[0]),l()):
  lis[i+1] = a
for _ in range(ka[1]):
  q = l()
  maxindex = []
  a = [[lis[a],a] for a in q if a in lis]
  maxv = max(a)
  for b in a:
    if maxv[0] == b[0]:
      maxindex.append(b)
  q.pop(q.index(maxv[1]))
  if len(maxindex) != 1:
    for m in maxindex:
      q.append(m[1])
  for a in q:
    saku.append(a)
print(len([a for a in lis if a not in saku]))
  
  
  

### FIXED CODE ###

import sys
input = sys.stdin.readline
def l(): return [int(a) for a in input().split(" ")] 
ka = l()
lis = {}
saku = []
for i,a in zip(range(ka[0]),l()):
  lis[i+1] = a
for _ in range(ka[1]):
  q = l()
  maxindex = []
  a = [[lis[a],a] for a in q if a in lis]
  maxv = max(a)
  for b in a:
    if maxv[0] == b[0]:
      maxindex.append(b)
  q.pop(q.index(maxv[1]))
  if len(maxindex) != 1:
    for m in maxindex:
      q.append(m[1])
  for a in q:
    saku.append(a)
saku = set(saku)
print(len([a for a in lis if a not in saku]))