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

from math import factorial as fac
N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
break_list.append( N + 1 )
start = 0
ans = 1
for i in break_list:
    sum_c = 0
    end = i - 1
    if start > end:
        i = -1
        break
    step_1 = end - start
    step_2 = int( ( end - start ) / 2 )
    for j in range(step_2 + 1):
        k = step_1 - 2 * j
        sum_c += fac(k+j) // ( fac(k) * fac(j) )
    ans *= sum_c
    start = i + 1
    
if i >= 0:
    print( ans % 1000000007 )
else:
    print(0)

### FIXED CODE ###

N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )

break_list.append(-10)
t = 0
fib = [0] * (N + 1)
if break_list[0] == 1:
    fib[1] = 0
    t += 1
else:
    fib[1] = 1
    
fib[0] = 1

for i in range(N - 1):
    if ( i + 2 ) ==  break_list[t]:
        fib[i + 2] = 0
        t += 1
    else:
        fib[i + 2] = fib[i] + fib[i + 1]
 
if N == 1:
    print( fib[1] )
else:
    print( fib[i+2] %  1000000007 )
### BUGGY CODE ###

from collections import defaultdict
n, m, q = map(int, input().split())
a, b, c, d = [0] * q, [0] * q, [0] * q, [0] * q
for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

ans = 0
for i in range(2 ** q):
    score = [0] * n
    flag = True
    cnt = 0
    for j in range(q):
        if i >> j & 1:
            score[b[j] - 1] = score[a[j] - 1] + c[j]
            cnt += d[j]
    for j in range(q):
        if i >> j & 1:
            if score[b[j] - 1] - score[a[j] - 1] != c[j]:
                flag = False
                break
    if flag == True:
        ans = max(ans, cnt)

print(ans)
    

### FIXED CODE ###


n, m, q = map(int, input().split())
a, b, c, d = [0] * q, [0] * q, [0] * q, [0] * q
score = [0] * n
ans = 0
for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

def calc_score(score):
    ret = 0
    for i in range(q):
        if score[b[i] - 1] - score[a[i] - 1] == c[i]:
            ret += d[i]
    return ret

def dfs(score, i, num):
    global ans
    if i == n:
        ans = max(ans, calc_score(score))
        return 
    for j in range(num, m + 1):
        score[i] = j
        dfs(score, i + 1, j)


dfs(score, 0, 1)
print(ans)
### BUGGY CODE ###

import sys
import fractions

sys.setrecursionlimit(10000000)
input=sys.stdin.readline

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

def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

def lcm(a, b):
    return a // fractions.gcd(a, b) * b

mod = 10**9+7

x=a[0]

for i in a[1:]:
    x=lcm(x,i)
ans=0
for i in range(n):
    ans+= x//a[i]%mod

print(ans%mod)


### FIXED CODE ###

import sys
import fractions

sys.setrecursionlimit(10000000)
input=sys.stdin.readline

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

def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

def lcm(a, b):
    return a // fractions.gcd(a, b) * b

mod = 10**9+7

x=a[0]

for i in a[1:]:
    x=lcm(x,i)
ans=0
for i in range(n):
    ans+= x//a[i]

print(ans%mod)
### BUGGY CODE ###

#encoding:utf-8

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

def factorint(N):
    table = {}
    while(N > 1):
        for i in range(2,N+1):
            if N%i == 0:
                while N%i == 0:
                    N = N//i
                    if i in table.keys():
                        table[i] += 1
                    else:
                        table[i] = 1
                break
    return table
ans = 1

if N < 40:
    facters = factorint(P)
    # print(facters)

    ans = 1
    for key in facters.keys():
        if facters[key]/N >= 1:
            ans *= key**(facters[key]//N)
print(int(ans))
# print(type(ans))


### FIXED CODE ###

#encoding:utf-8

import math

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

def factorint(N):
    table = {}
    while(N > 1):
        for i in range(2,N+1):
            if N%i == 0:
                while N%i == 0:
                    N = N//i
                    if i in table.keys():
                        table[i] += 1
                    else:
                        table[i] = 1
                break
    return table

ans = 1
if N == 1:
    ans = P
elif 1 < N < 40:
    for i in range(2,round(P**(1/N))+1):
        if P % i**N == 0:
            ans = i

else:
    pass

print(int(ans))
# print(type(ans))
### BUGGY CODE ###

from collections import Counter

N = int(input())
X = input()
int_X = int(X, 2)


def pop_counter(n):
    return n % Counter(bin(n))['1']


ans = 0
for n, i in enumerate(X):
    ans = 0
    if i == '1':
        tmp = int_X - pow(2, N - 1 - n)
    else:
        tmp = int_X + pow(2, N - 1 - n)
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)


### FIXED CODE ###

N = int(input())
X = input()
bin_X = int(X, 2)
cnt = 0
for i in X:
    if i == '1':
        cnt += 1


def bit_count(bits):
    cnt = 0
    while bits:
        bits = bits & (bits - 1)
        bits >> 1
        cnt += 1
    return cnt


def pop_counter(n):
    return n % bit_count(n)


ans = 0
xp = bin_X % (cnt + 1)
if cnt != 1:
    xm = bin_X % (cnt - 1)
else:
    xm = 0
for n, i in enumerate(X):
    if i == '0':
        tmp = xp + pow(2, N - n - 1, cnt + 1)
        tmp %= cnt + 1
    elif cnt != 1:
        tmp = xm - pow(2,N-n-1,cnt-1)
        tmp %= cnt -1
    else:
        print(0)
        continue
    ans = 1
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)
### BUGGY CODE ###

s = input()
t = input()
n = max(len(s),len(t))
dp = [[0]*(n+1) for i in range(n+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1])

ans = ""
i = len(s)
j = len(t)
while (i > 0 and j > 0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
print(ans)
        

### FIXED CODE ###

s = input()
t = input()
n = max(len(s),len(t))
dp = [[0]*(n+1) for i in range(n+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1])

ans = ""
i = len(s)
j = len(t)
while (i > 0 and j > 0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
print(ans)
### BUGGY CODE ###

def solve(N, W, weight_values):
      dp = [0 for _ in range(W + 1)]
     
      for i in range(N):
        wi, vi = weight_values[i]
        for w in range(W, wi - 1, -1): # loop from W down to wi
          if dp[w - wi] + vi > dp[w]:
            dp[w] = dp[w - wi] + vi
     
      print(dp[W])
    
def iln(): return list(map(int, input().split()))

N, W = iln()
w_v = []
for i in range(N):
	w_v.append(iln())

solve(N, W, w_v)

### FIXED CODE ###


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0
 
for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))
### BUGGY CODE ###

n,a,b = map(int,input().split())
# nCr(r:1~n)-nCa-nCb
mod = 10**9+7
def comb(n,r):
    res = 1
    for i in range(1,n+1):
        res = res*i%mod
    for i in range(1,r+1):
        res = res*pow(i,mod-2,mod)%mod
    for i in range(1,n-r+1):
        res = res*pow(i,mod-2,mod)%mod
    return res
ans = 0
for i in range(1,n+1):
    ans = (ans+comb(n,i))%mod
print((ans-comb(n,a)-comb(n,b))%mod)

### FIXED CODE ###

n,a,b = map(int,input().split())
mod = 10**9+7
from functools import reduce

def comb(r):
    num = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    dem = reduce(lambda x, y: x * y % mod, [k+1 for k in range(r)])
    return num*pow(dem,mod-2,mod)%mod

ans = (pow(2,n,mod)-1-comb(a)-comb(b))%mod
print(ans)
### BUGGY CODE ###

N = int(input())
s = [input() for i in range(N)]
ans = 0
str_list = []
for i in range(N):
  str_list.append(sorted(s[i]))
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    if str_list[i] == str_list[j]:
      ans += 1
print(int(ans/2))

### FIXED CODE ###

n = int(input())
ans = 0
dict = {}
for _ in range(n):
  	#文字列をキーとする辞書型に出現回数を保持する
    s = str(''.join(sorted(list(input()))))
    try:
        ans += dict[s]
        dict[s] += 1
    except:
        dict[s] = 1
print(ans)
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = Counter(list(map(int, input().split())))
cnt = 0
for i in range(len(a)):
    if a.most_common()[i][1]-a.most_common()[i][0] < 0:
        cnt += a.most_common()[i][1]
    else:
        cnt += a.most_common()[i][1]-a.most_common()[i][0]
print(cnt)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = Counter(list(map(int, input().split())))
cnt = 0
for k, v in Counter(a).items():
    if k > v:
        cnt += v
    else:
        cnt += (v-k)
print(cnt)
### BUGGY CODE ###

INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    D = [[INF if i != j else 0 for i in range(j + 1)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        a = min(lst[1],lst[2])
        b = max(lst[1],lst[2])
        if D[b - 1][a - 1] >= INF:
          print(-1)
        else:
          print(D[b - 1][a - 1])
      elif lst[0] == 1:
        a = min(lst[1],lst[2])
        b = max(lst[1],lst[2])
        D[b-1][a-1] = min(D[b-1][a-1],lst[3])
        for i in range(n):
          for j in range(0,i + 1):
            D[i][j] = min(D[i][j],D[max(i,a-1)][min(i,a-1)] + lst[3] + D[max(j,b-1)][min(j,b-1)],D[max(i,b-1)][min(i,b-1)] + lst[3] + D[max(j,a-1)][min(j,a-1)])
  except EOFError:
    break


### FIXED CODE ###

from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break
### BUGGY CODE ###

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

def maximum_profit(price_list):
    max = price_list[1] - price_list[0]
    for x in range(len(price_list)-1):
        for y in range(x+1, len(price_list)):
            if max < price_list[y] - price_list[x]:
                max = price_list[y] - price_list[x]
    return max

input_num = int(input())
price_list = list()
for i in range(input_num):
    input_price = int(input())
    price_list.append(input_price)
print(maximum_profit(price_list))

### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    maxv = -10 ** 9
    minv = int(input())

    for _ in range(1, n):
        temp = int(input())
        maxv = temp - minv if temp - minv > maxv else maxv
        minv = temp if temp < minv else minv

    print(maxv)
### BUGGY CODE ###

n = int(input())
a = []
max_list = []
max_i = 0

for i in range(n):
    a.append(str(input()))

a2 = a
for i in set(a2):
    if max_i < a.count(i):
        max_list = [i]
        max_i = a.count(i)
    elif max_i == a.count(i):
        max_list.append(i)

max_list.sort()

for i in max_list:
    print(i)       
    

### FIXED CODE ###

import collections

n = int(input())
a = []
max_list = []
max_i = 1

a = [str(input()) for x in range(n)]

c = collections.Counter(a)
c = c.most_common()
max_i = c[0][1]

for i in range(len(c)):
    if max_i == c[i][1]:
        max_list.append(c[i][0])
    else:
        break

max_list.sort()

for i in max_list:
    print(i)
### BUGGY CODE ###

N  =int(input())
p = 1
for i in range(1,N+1):
    p = p*i
print(p%(10**9+7))

### FIXED CODE ###

N  =int(input())
p = 1
for i in range(1,N+1):
    p = p*i
    p = p%(10**9+7)
print(p%(10**9+7))
### BUGGY CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [tuple(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(tuple(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    for i in ans:
        print(i)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


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

import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))

def main():
    h, w = MII()
    ss = []
    for i in range(h):
        ss.append(IS())
    

    L = [[0]*w for _ in range(h)]
    R = [[0]*w for _ in range(h)]
    D = [[0]*w for _ in range(h)]
    U = [[0]*w for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if ss[i][j] == '#': L[i][j] = 0; continue
            if j == 0: L[i][j] = 1; continue
            if j > 0: L[i][j] = L[i][j-1] + 1; continue

    for i in range(h):
        for j in reversed(range(w)):
            if ss[i][j] == '#': R[i][j] = 0; continue
            if j == w-1: R[i][j] = 1; continue
            if j < w-1: R[i][j] = R[i][j+1] + 1; continue

    for i in range(h):
        for j in range(w):
            if ss[i][j] == '#': D[i][j] = 0; continue
            if i == 0: D[i][j] = 1; continue
            if i > 0: D[i][j] = D[i-1][j] + 1; continue

    for i in reversed(range(h)):
        for j in range(w):
            if ss[i][j] == '#': U[i][j] = 0; continue
            if i == h-1: U[i][j] = 1; continue
            if i < h-1: U[i][j] = U[i+1][j] + 1; continue

    maxv = 0
    for i in range(h):
        for j in range(w):
            maxv = max(maxv, L[i][j]+R[i][j]+D[i][j]+U[i][j]-3)
    print(maxv)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))

def main():
    h, w = MII()
    ss = []
    for i in range(h):
        ss.append(IS())
    

    L = [[0]*w for _ in range(h)]
    R = [[0]*w for _ in range(h)]
    D = [[0]*w for _ in range(h)]
    U = [[0]*w for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if ss[i][j] == '#': L[i][j] = 0; continue
            if j == 0: L[i][j] = 1; continue
            if j > 0: L[i][j] = L[i][j-1] + 1; continue

    for i in range(h):
        for j in reversed(range(w)):
            if ss[i][j] == '#': R[i][j] = 0; continue
            if j == w-1: R[i][j] = 1; continue
            if j < w-1: R[i][j] = R[i][j+1] + 1; continue

    for i in range(h):
        for j in range(w):
            if ss[i][j] == '#': D[i][j] = 0; continue
            if i == 0: D[i][j] = 1; continue
            if i > 0: D[i][j] = D[i-1][j] + 1; continue

    for i in reversed(range(h)):
        for j in range(w):
            if ss[i][j] == '#': U[i][j] = 0; continue
            if i == h-1: U[i][j] = 1; continue
            if i < h-1: U[i][j] = U[i+1][j] + 1; continue

    maxv = 0
    for i in range(h):
        for j in range(w):
            maxv = max(maxv, L[i][j]+R[i][j]+D[i][j]+U[i][j]-3)
    print(maxv)

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

n=int(input())

a=0
for i in range(len(str(n))):
    a+=int(str(n)[i])


if a%9==0:
    print("Yes")

else:
    print("No")

### FIXED CODE ###

n=int(input())


if n%9==0:
    print("Yes")

else:
    print("No")
### BUGGY CODE ###

# atcoder https://atcoder.jp/contests/dp/tasks/dp_d

N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    wi, vi = map(int, input().split())
    w.append(wi)
    v.append(vi)


dp = [[0 for j in range(W+1)] for i in range(N+1)]

for i in range(1, N+1):
    for j in range(1, W+1):
        if j >= w[i-1]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

### FIXED CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_d

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, W = MAP()
w, v = [], []
for _ in range(N):
    wi, vi = MAP()
    w.append(wi)
    v.append(vi)

DP = [[0] * (N+1) for _ in range(W+1)]

for i in range(1, W+1):
    for j in range(1, N+1):
        if i < w[j-1]:
            DP[i][j] = max(
                DP[i][j-1],
                DP[i-1][j])
        else:
            DP[i][j] = max(
                DP[i][j-1],
                DP[i-w[j-1]][j-1] + v[j-1],
                DP[i-1][j])

print(DP[-1][-1])
### BUGGY CODE ###

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


def get_path(u, v):
    stack = [u]
    prev = [None] * (N+1)
    visited = [False] * (N+1)
    visited[u] = True
    while stack:
        node = stack.pop()
        for next, i in G[node]:
            if not visited[next]:
                visited[next] = True
                prev[next] = (node, i)
                stack.append(next)
    path = 0
    node = v
    while node != u:
        p, i = prev[node]
        node = p
        path += 1 << i
    return path


def count(bits, N):
    cnt = 0
    for i in range(N):
        if ((bits >> i) & 1) == 1:
            cnt += 1
    return cnt


M = int(input())
uv = [tuple(map(int, input().split())) for _ in range(M)]
paths = [get_path(u, v) for u, v in uv]
ans = 2**(N-1)
for bit in range(1, 1 << M):
    cnt = 0
    tmp = 0
    for i in range(M):
        if ((bit >> i) & 1) == 1:
            cnt += 1
            tmp |= paths[i]
    ans += (-1)**cnt * 2**(N-1-count(tmp, N-1))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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


def get_path(u, v):
    stack = [u]
    prev = [None] * (N+1)
    visited = [False] * (N+1)
    visited[u] = True
    while stack:
        node = stack.pop()
        for next, i in G[node]:
            if not visited[next]:
                visited[next] = True
                prev[next] = (node, i)
                stack.append(next)
    path = 0
    node = v
    while node != u:
        p, i = prev[node]
        node = p
        path += 1 << i
    return path


def count(bits, N):
    cnt = 0
    for i in range(N):
        if ((bits >> i) & 1) == 1:
            cnt += 1
    return cnt


M = int(input())
uv = [tuple(map(int, input().split())) for _ in range(M)]
paths = [get_path(u, v) for u, v in uv]
ans = 2**(N-1)
for bit in range(1, 1 << M):
    cnt = 0
    tmp = 0
    for i in range(M):
        if ((bit >> i) & 1) == 1:
            cnt += 1
            tmp |= paths[i]
    ans += (-1)**cnt * 2**(N-1-count(tmp, N-1))
print(ans)
### BUGGY CODE ###

import sys

class UnionFind():
    def __init__(self, num, V):
        self.par = [-1]*num
        self.size = [1]*num
        self.unused = [0]*num
        self.cost = V
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return 0
        rx, ry = sorted((rx, ry))
        self.par[ry] = rx
        self.size[rx] += self.size[ry]
        self.cost[rx] += self.cost[ry]
        self.unused[rx] += self.unused[ry]
        self.unused[ry] = 0
        return 1

def inpl() : return list(map(int, input().split()))
input = sys.stdin.readline

N, M = inpl()
X = inpl()
Edge = []
for _ in range(M):
    a, b, y = inpl()
    a -= 1
    b -= 1
    Edge.append((y, a, b))

Edge.sort()
Tr = UnionFind(N, X)
for y, a, b in Edge:
    Tr.union(a, b)
    pa = Tr.find(a)
    if Tr.cost[pa] >= y:
        Tr.unused[pa] = 0
    else:
        Tr.unused[pa] += 1

print(sum(Tr.unused))

### FIXED CODE ###

import sys

class UnionFind():
    def __init__(self, num, V):
        self.par = [-1]*num
        #self.size = [1]*num
        self.unused = [0]*num
        self.cost = V
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return 0
        if ry > rx:
            rx, ry = ry, rx
        self.par[ry] = rx
        #self.size[rx] += self.size[ry]
        self.cost[rx] += self.cost[ry]
        self.unused[rx] += self.unused[ry]
        self.unused[ry] = 0
        return 1

def solve():
    
    N, M = map(int, input().split())
    X = list(map(int, sys.stdin.readline().split()))
    Edge = [None]*M
    for i in range(M):
        a, b, y = list(map(int, sys.stdin.readline().split()))
        Edge[i] = (y, a-1, b-1)
    
    Edge.sort()
    Tr = UnionFind(N, X)
    for y, a, b in Edge:
        Tr.union(a, b)
        pa = Tr.find(a)
        if Tr.cost[pa] >= y:
            Tr.unused[pa] = 0
        else:
            Tr.unused[pa] += 1
    
    print(sum(Tr.unused))
    return

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

N = int(input())
A = list(map(int, input().split()))
fumidai_list, A_after = [], 0

for count_a in range(len(A)):
    fumidai = 0

    if(A[count_a] >= A_after):
        A_after = A[count_a]
        fumidai_list.append(fumidai)

    elif(A[count_a] < A_after):

        while True:
            fumidai = fumidai + 1
            A[count_a] = A[count_a] + fumidai
            if(A[count_a] >= A_after):
                break

        fumidai_list.append(fumidai)

print(sum(fumidai_list))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
fumidai_list, A_after = [], 0

for count_a in range(len(A)):
    fumidai = 0

    if(A[count_a] >= A_after):
        A_after = A[count_a]
        fumidai_list.append(fumidai)

    elif(A[count_a] < A_after):
        fumidai = A_after - A[count_a]
        fumidai_list.append(fumidai)

print(sum(fumidai_list))