Harryxun/stf_run huggingface dataset:
import math


def comb(n, r):
    if n < r or r < 0:
        return 0
    nume = 1
    deno = 1
    for i in range(1, r + 1):
        nume *= (n - i + 1)
        deno *= (i)
    return nume//deno


def solve(N, K):
    if K == 0:
        return 1
    keta = math.floor(math.log(N, 10)) + 1
    x = N//pow(10, keta-1)
    ret = 0
    if K > keta:
        return 0
    # ptn1: 最大の桁は0
    if keta != K:
        ret += comb(keta - 1, K) * (9 ** K)
    # ptn2: 最大の桁はNのその桁の値未満
    ret += (x-1)*comb(keta-1, K-1)*pow(9, K-1)
    # ptn3: 最大の桁はNのその桁の値
    ret += solve(N % pow(10, keta-1), K - 1)
    return ret


N = int(input())
K = int(input())
ans = solve(N, K)
print(ans)


### FIXED CODE ###

import math


def comb(n, r):
    if n < r or r < 0:
        return 0
    nume = 1
    deno = 1
    for i in range(1, r + 1):
        nume *= (n - i + 1)
        deno *= (i)
    return nume//deno


def solve(N, K):
    if N < K:
        return 0
    if K == 0:
        return 1
    keta = math.floor(math.log(N, 10)) + 1
    x = N//pow(10, keta-1)
    ret = 0
    if K > keta:
        return 0
    # ptn1: 最大の桁は0
    if keta != K:
        ret += comb(keta - 1, K) * (9 ** K)
    # ptn2: 最大の桁はNのその桁の値未満
    ret += (x-1)*comb(keta-1, K-1)*pow(9, K-1)
    # ptn3: 最大の桁はNのその桁の値
    ret += solve(N % pow(10, keta-1), K - 1)
    return ret


N = int(input())
K = int(input())
ans = solve(N, K)
print(ans)
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur])
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [99999999] * (n+1)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

sys.setrecursionlimit(230000)
import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur], 0, lis+1)
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [999999999999] * (n+2)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

a,b,c = sorted(map(int,input().split()))
print (a + b)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

a, b, c = map(int,readline().split())
print(min(a + b, b + c, c + a))
import sys

sys.setrecursionlimit(10000)


class Dp:

    def __init__(self, size):
        self.size = size
        self.array = [0] * (size+1)

    def calc(self, n):
        if n == 1:
            return 1
        if self.array[n] != 0:
            return self.array[n]
        self.array[n] = self.calc(n//2) * 2 + 1
        return self.array[n]


def main():
    h = int(input())
    dp = Dp(h)
    result = dp.calc(h)
    print(result)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(20000)


class Dp:

    def __init__(self, size):
        self.size = size

    @lru_cache(maxsize=None)
    def calc(self, n):
        if n == 1:
            return 1
        return self.calc(n//2) * 2 + 1


def main():
    h = int(input())
    dp = Dp(h)
    result = dp.calc(h)
    print(result)


if __name__ == "__main__":
    main()
D = int(input())#D=365
c = list(map(int, input().split()))#0<=c<=100
s = [list(map(int, input().split())) for _ in range(D)]#0<=s<=20000

t = [int(input()) for _ in range(D)]

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

INF = 10**9


def culc_value(t):
    last = [0] * 26
    value = 0
    for d in range(D):
        type = t[d]
        value += s[d][type - 1]
        last[type - 1] = d + 1
        for i in range(26):
            value -= c[i] * (d + 1 - last[i])
    return value


v_lastday = []
value = culc_value(t)

for d, q in dq:
    value = value - s[d - 1][t[d - 1]] + s[d - 1][q - 1]

    # qに変換後のマイナス計算
    q_prev = 0
    q_next = 365
    for i in range(D):
        if t[i] == q and i + 1 != d:
            if q_prev < d:
                q_prev = i + 1
                continue
            elif d < q_next:
                q_next = i + 1
                break
    x = q_next - q_prev
    value += ((x + 1) * x // 2) * c[q - 1]
    y = d - q_prev
    z = q_next - d
    value -= (((y + 1) * y // 2) + (z + 1) * z // 2) * c[q - 1]

    # 変換前のt[d-1]のマイナス計算を直す
    r = t[d-1]
    r_prev = 0
    r_next = 365
    for i in range(D):
        if t[i] == r and i + 1 != d:
            if r_prev < d:
                r_prev = i + 1
                continue
            elif d < r_next:
                r_next = i + 1
                break
    x = r_next - r_prev
    value -= ((x + 1) * x // 2) * c[r - 1]
    y = d - r_prev
    z = r_next - d
    value += (((y + 1) * y // 2) + (z + 1) * z // 2) * c[r - 1]

    t[d - 1] = q
    v_lastday.append(value)

for x in v_lastday:
    print(x)


"""
for i in range(D):
    print(v[i])
"""

### FIXED CODE ###

D = int(input())#D=365
c = [0] + list(map(int, input().split()))#0<=c<=100
s = [0] + [[0] + list(map(int, input().split())) for _ in range(D)]#0<=s<=20000

t = [0] + [int(input()) for _ in range(D)]

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


held = [[0] for _ in range(27)]
def culc_value(t):
    last = [0] * 27
    value = 0
    for d in range(1, D+1):
        type = t[d]
        held[type].append(d)
        value += s[d][type]
        last[type] = d
        for i in range(1, 27):
            value -= c[i] * (d - last[i])
    for i in range(1, 27):
        held[i].append(D+1)
    #print(held)
    return value


v_lastday = []
value = culc_value(t)

for d, q in dq:
    value += - s[d][t[d]] + s[d][q]

    # 変換前のt[d-1]のマイナス計算を直す
    ind = held[t[d]].index(d)
    r = held[t[d]][ind+1]
    l = held[t[d]][ind-1]
    x = r - l
    value -= ((x + 1) * x // 2) * c[t[d]]
    y = d - l
    z = r - d
    value += (((y + 1) * y // 2) + (z + 1) * z // 2) * c[t[d]]

    del held[t[d]][ind]
    t[d] = q
    held[q].append(d)
    held[q] = sorted(held[q])
    #print(held[q])

    # qに変換後のマイナス計算
    ind = held[q].index(d)
    r = held[q][ind+1]
    l = held[q][ind-1]
    x = r - l
    value += ((x + 1) * x // 2) * c[q]
    y = d - l
    z = r - d
    value -= (((y + 1) * y // 2) + (z + 1) * z // 2) * c[q]

    v_lastday.append(value)

for ans in v_lastday:
    print(ans)
N,Q =map(int,input().strip().split())
#=int(input().strip())
#=list(map(int,input().strip().split()))
S = input()

count = [0]
for i in range(0,N ):
    if S[i] == "A" and S[i + 1] == "C":
        count.append(count[i] + 1)
    else:
        count.append(count[i])


for i in range(0,Q):
    l,r = map(int,input().strip().split())
    if r > len(count):
        r = len(count)
    if l == 0:
        l += 1
    print(count[r - 1] - count[l - 1])



### FIXED CODE ###

N,Q =map(int,input().strip().split())
#=int(input().strip())
#=list(map(int,input().strip().split()))
S = input()

count = [0]
for i in range(0,N - 1):
    if S[i] == "A" and S[i + 1] == "C":
        count.append(count[i] + 1)
    else:
        count.append(count[i])


for i in range(0,Q):
    l,r = map(int,input().strip().split())
    if r > len(count):
        r = len(count)
    if l == 0:
        l += 1
    print(count[r - 1] - count[l - 1])
#nの約数を列挙する関数
def n_div(n):
    div_list = []
    import math
    for i in range(1, math.ceil(math.sqrt(n))+1):
        if n % i ==0:
            div_list.append(i)
            if i*i ==n:
                continue
            div_list.append(n//i)
    div_list.sort()
    return div_list

n = int(input())
lr = n_div(n)
#print(lr)
if len(lr) % 2==0:
    a = len(lr)/2
    a = int(a)
    ans = lr[a]+lr[a-1]-2
else:
    a = math.floor(len(lr)/2)
    #print(a)
    ans = lr[a]*2  -2
    
print(ans)

### FIXED CODE ###

#nの約数を列挙する関数
import math
def n_div(n):
    div_list = []
    import math
    for i in range(1, math.ceil(math.sqrt(n))+1):
        if n % i ==0:
            div_list.append(i)
            if i*i ==n:
                continue
            div_list.append(n//i)
    div_list.sort()
    return div_list

n = int(input())
lr = n_div(n)
#print(lr)
if len(lr) % 2==0:
    a = len(lr)/2
    a = int(a)
    ans = lr[a]+lr[a-1]-2
else:
    a = math.floor(len(lr)/2)
    #print(a)
    ans = lr[a]*2  -2
    
print(ans)
x, y = [int(i) for i in input().split()]

if x == y == 2:
  print("Yes")
elif x in (4, 6, 9, 11) and y in (4, 6, 9, 11):
  print("Yes")
elif x in (1, 3, 5, 7, 8, 10, 12) and y in (1, 3, 5, 7, 8, 10, 12):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

x, y = [int(i) for i in input().split()]

if x == y == 2:
  print("Yes")
elif x in (4, 6, 9, 11) and y in (4, 6, 9, 11):
  print("Yes")
elif x in (1, 3, 5, 7, 8, 10, 12) and y in (1, 3, 5, 7, 8, 10, 12):
  print("Yes")
else:
  print("No")
import sys
n = int(sys.argv[1])
a = int(sys.argv[2])
b = int(sys.argv[3])
print(min(a*n, b))

### FIXED CODE ###

import sys
n, a, b = [int(x) for x in input().split()]
print(min(a*n, b))
a,b=map(float,input().split())
tempb=int(floor(b)*1000)
print(int(a*tempb)//1000)


### FIXED CODE ###

a,b=map(str,input().split())
tempb=int(float(b)*1000)
tempa=int(a)
print(int(tempa*tempb)//1000)
n, m = map(int, input().split())
g = [[] for _  in range(n)]
for _ in range(m):
  x, y = map(int, input().split())
  x, y = x -1, y-1
  g[x].append(y)  

# dp[v]: ノードvを起点にしたときの、Gの有効パスの長さの最大値
dp = [-1]*n
def rec(v):
  if dp[v] != -1:
    return dp[v]
  else:
    res = 0
    for u in g[v]:
      res = max(res, rec(u)+1)
    dp[v] = res
    return dp[v]
  
for i in range(n):
  rec(i)
print(max(dp))

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
g = [[] for _  in range(n)]
for _ in range(m):
  x, y = map(int, input().split())
  x, y = x -1, y-1
  g[x].append(y)  

# dp[v]: ノードvを起点にしたときの、Gの有効パスの長さの最大値
dp = [-1]*n
def rec(v):
  if dp[v] != -1:
    return dp[v]
  else:
    res = 0
    for u in g[v]:
      res = max(res, rec(u)+1)
    dp[v] = res
    return dp[v]
  
for i in range(n):
  rec(i)
print(max(dp))
N = int(input())
S = ["*"]*(N+1)
S[1:] = list(input())
Q = int(input())
q1,q2,q3 = [0]*Q,[0]*Q,[0]*Q
for i in range(Q):
    tmp = input().split()
    q1[i],q2[i] = map(int,tmp[:2])
    if q1[i] == 2:
        q3[i] = int(tmp[2])
    else:
        q3[i] = tmp[2]

class BIT:
    def __init__(self, n, init_list):
        self.num = n + 1
        self.tree = [0] * self.num
        for i, e in enumerate(init_list):
            self.update(i, e)

    #a_kにxを加算
    def update(self, k, x):
        k = k + 1
        while k < self.num:
            self.tree[k] += x
            k += (k & (-k))
        return

    def query1(self, r):
        ret = 0
        while r > 0:
            ret += self.tree[r]
            r -= r & (-r)
        return ret

    #通常のスライスと同じ。lは含み、rは含まない
    def query2(self, l, r):
        return self.query1(r) - self.query1(l)

s_pos = [BIT(N+1,[0]*(N+1)) for _ in range(26)]

for i in range(1,N+1):
    s_pos[ord(S[i]) - ord("a")].update(i,1)

alphabets = [chr(ord("a") + i) for i in range(26)]

for i in range(Q):
    if q1[i] == 1:
        s_pos[ord(S[q2[i]]) - ord("a")].update(q2[i],-1)
        S[i] = q3[i]
        s_pos[ord(q3[i]) - ord("a")].update(q2[i],1)
    else:
        ans = 0
        for c in alphabets:
            if s_pos[ord(c) - ord("a")].query2(q2[i],q3[i]+1) > 0:
                ans += 1
        print(ans)











### FIXED CODE ###

N = int(input())
S = ["*"]*(N+1)
S[1:] = list(input())
Q = int(input())
q1,q2,q3 = [0]*Q,[0]*Q,[0]*Q
for i in range(Q):
    tmp = input().split()
    q1[i],q2[i] = map(int,tmp[:2])
    if q1[i] == 2:
        q3[i] = int(tmp[2])
    else:
        q3[i] = tmp[2]

class BIT:
    def __init__(self, n, init_list):
        self.num = n + 1
        self.tree = [0] * self.num
        for i, e in enumerate(init_list):
            self.update(i, e)

    #a_kにxを加算
    def update(self, k, x):
        k = k + 1
        while k < self.num:
            self.tree[k] += x
            k += (k & (-k))
        return

    def query1(self, r):
        ret = 0
        while r > 0:
            ret += self.tree[r]
            r -= r & (-r)
        return ret

    #通常のスライスと同じ。lは含み、rは含まない
    def query2(self, l, r):
        return self.query1(r) - self.query1(l)

s_pos = [BIT(N+1,[0]*(N+1)) for _ in range(26)]

for i in range(1,N+1):
    s_pos[ord(S[i]) - ord("a")].update(i,1)

alphabets = [chr(ord("a") + i) for i in range(26)]

for i in range(Q):
    if q1[i] == 1:
        s_pos[ord(S[q2[i]]) - ord("a")].update(q2[i],-1)
        S[q2[i]] = q3[i]
        s_pos[ord(q3[i]) - ord("a")].update(q2[i],1)
    else:
        ans = 0
        for c in alphabets:
            if s_pos[ord(c) - ord("a")].query2(q2[i],q3[i]+1) > 0:
                ans += 1
        print(ans)
mod = 998244353

def comb(n, r):
    if 2 * r > n: return comb(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % mod

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

fac = [1] * (n+2)
inv = [1] * (n+2)
for i in range(2, n+1):
    fac[i] = fac[i-1] * i % mod
inv[n] = pow(fac[n], mod - 2, mod)
for i in range(n-1, 1, -1):
    inv[i] = inv[i + 1] * (i + 1) % mod

ans = 0
for i in range(n+1):
    if (k-a*i) > 0 and (k-a*i)%b == 0 :
      j = (k-a*i)//b 
      ans += comb(n, i) * comb(n, j)% mod

print(ans)

### FIXED CODE ###

mod = 998244353

def comb(n, r):
    if 2 * r > n: return comb(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % mod

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

fac = [1] * (n+2)
inv = [1] * (n+2)
for i in range(2, n+1):
    fac[i] = fac[i-1] * i % mod
inv[n] = pow(fac[n], mod - 2, mod)
for i in range(n-1, 1, -1):
    inv[i] = inv[i + 1] * (i + 1) % mod

ans = 0
for i in range(n+1):
    Num = (k-a*i)
    if (0 <= Num//b) and (Num//b <= n) and (Num%b == 0):
      j = Num//b 
      ans += comb(n, i) * comb(n, j) 
print(ans%mod)
n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

def frog(n, k, h):
    d = [float('inf')] * n
    d[0] = 0

    for i in range(1, n):
        d[i] = min(
            d[j] + abs(h[i] - h[j]) for j in range(max(i - k, 0), i)
        )
    return d[n - 1]


print(frog(n, k, h))


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
dp = [10 ** 9] * N
dp[0] = 0

for i in range(N):
  if i + 1 < N: dp[i + 1] = min(dp[i + 1], dp[i] + abs(H[i] - H[i + 1]))
  if i + 2 < N: dp[i + 2] = min(dp[i + 2], dp[i] + abs(H[i] - H[i + 2]))

print(dp[-1])
import math

price = input()
payment = math.ceil(float(price) / 1000) * 1000
result = payment - price
print(int(result))

### FIXED CODE ###

import math

price = int(input())
payment = math.ceil(float(price) / 1000) * 1000
result = payment - price
print(int(result))
A=map(int,input().split())
n=int(A[0])
m=int(A[1])


max=[]
k=0
while n>0 and m>0:
    B=[0 for i in range(n)]
    B=input().split()
    for i in range(n):
        B[i]=int(B[i])
    ma=0
    for i in range(n):
        for j in range(i+1,n):  
            x=0 
            x=B[i]+B[j]
            if ma<x and x<=m:
                ma=x
    max.append(ma)
    A=input().split()
    n=int(A[0])
    m=int(A[1])
    k+=1
for i in range(k):
    if max[i]>0:
        print(max[i])
    else:
        print("NONE")


### FIXED CODE ###

A=[0 for i in range(2)]
A=input().split()
n=int(A[0])
m=int(A[1])
max=[]
k=0

while n>0 and m>0:
    B=[0 for i in range(n)]
    B=input().split()
    for i in range(n):
        B[i]=int(B[i])
    max1=0
    for i in range(n):
        for j in range(i+1,n):  
            x=0 
            x=B[i]+B[j]
            if max1<x and x<=m:
                max1=x
    max.append(max1)
    A=input().split()
    n=int(A[0])
    m=int(A[1])
    k+=1
for i in range(k):
    if max[i]>0:
        print(max[i])
    else:
        print("NONE")
import sys
from fractions import gcd

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def merge(a, b):
    g = gcd(a, b)
    a //= g
    b //= g
    if a % 2 == 0:
        return 0
    if b % 2 == 0:
        return 0
    n = a * b * g
    if n > 10 ** 9:
        return 0
    return n


n, m = map(int, readline().split())
a = list(map(int, readline().split()))

a = [x >> 1 for x in a]

for i in range(n-1):
    a[i+1] = int(a[i] * a[i+1] / merge(a[i], a[i+1]))

if a[n-1] > 10**9:
    print("0")
else:
    t = m // a[i+1]
    ans = (m // a[i+1]) - (m // (a[i+1] * 2))
    print(ans)


### FIXED CODE ###

from fractions import gcd
from functools import reduce

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M, *A = map(int, read().split())
 
# 「奇数倍」に帰着
A = [x >> 1 for x in A]
 

def merge(a, b):
    g = gcd(a, b)
    a //= g
    b //= g
    if a % 2 == 0:
        return 0
    if b % 2 == 0:
        return 0
    n = a * b * g
    if n > 10 ** 9:
        return 0
    return n


x = reduce(merge, A)

if x == 0:
    answer = 0
else:
    answer = (M//x) - (M//(x+x))
 
print(answer)
mod = 10 ** 9 + 7
fact = [i for i in range(10**5)]
fact[0] = 1
for i in range(10 ** 5-1):
  fact[i+1] *= fact[i]
  fact[i+1] %= mod
n,m = map(int,input().split())
if abs(n-m)>1:
  print(0)
else:
  if n!=m:
    print(fact[n]*fact[m]%mod)
  else:
    print(fact[n]*fact[m]*2%mod)

### FIXED CODE ###

mod = 10 ** 9 + 7
fact = [i for i in range(10**5+1)]
fact[0] = 1
for i in range(10 ** 5):
  fact[i+1] *= fact[i]
  fact[i+1] %= mod
n,m = map(int,input().split())
if abs(n-m)>1:
  print(0)
else:
  if n!=m:
    print(fact[n]*fact[m]%mod)
  else:
    print(fact[n]*fact[m]*2%mod)
n=int(input())
a=0
for i in range(len(a)):
    a+=str(n)[i]
if n%a==0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n=int(input())
a=0
for i in range(len(str(n))):
    a+=int(str(n)[i])
if n % a== 0:
    print("Yes")
else:
    print("No")
import math
#x a bを設定する
x,a,b = map(int,input().split())
#x からaまでの距離とxからbまでの距離を計算する
a_distant = math.sqrt((a - x)^2)
b_distant = math.sqrt((b - x)^2)
#aまでとbまでを比較して短い方を出力する
if a_distant > b_distant:
    print("B")
else:
    print("A")

### FIXED CODE ###

import math
#x a bを設定する
x,a,b = map(int,input().split())
#x からaまでの距離とxからbまでの距離を計算する

a_distant = a - x
b_distant = b - x
if a_distant < 0:
    a_distant = a_distant*(-1)
if b_distant < 0:
    b_distant = b_distant*(-1)
#aまでとbまでを比較して短い方を出力する
if a_distant > b_distant:
    print("B")
else:
    print("A")
a, b = int(input(x) for x in input().split())
print((a+b)/2, (a+b)*2)



### FIXED CODE ###

a, b = (int(x) for x in input().split())
area = a*b
perimeter = (a+b)*2
print(area, perimeter)
input = [iint(i) for i in input().split(" ")]
print(input[0]*input[1], input[0]*2+input[1]*2)

### FIXED CODE ###

x,y = [int(i) for i in input().split()]
area = x*y
length = (x*2)+(y*2)
print(area,length)
import sys
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
*X, = map(int, input().split())
E = []
for i in range(M):
    a, b, y = map(int, input().split())
    E.append((y, a-1, b-1))
E.sort()

*p, = range(N)
Y = [0]*M; Z = [0]*M
A = X[:]
B = [0]*M
C = [-1]*M
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
        A[px] += A[py]
    else:
        p[px] = py
        A[py] += A[px]
    return 1

G = [None for i in range(M)]

ans = 0
for i, (y, a, b) in enumerate(E):
    pa = root(a); pb = root(b)
    ca = C[pa]; cb = C[pb]
    if unite(a, b):
        pa = root(a)
        Z[i] = 1
        B[i] = A[pa]
        C[pa] = i
        #print(">", i, pa, pb, A[pa], y)
        if A[pa] < y:
            G[i] = []
            if ca != -1:
                G[i].append(ca)
            if cb != -1:
                G[i].append(cb)
    else:
        if A[pa] < y:
            G[i] = []
            if ca != -1:
                G[i].append(ca)
            C[pa] = i

sx = sum(X)
#print(Z)

from collections import deque
que = deque()
if sx < E[C[0]][0]:
    que.append(C[0])
#print(G, C)
while que:
    v = que.popleft()
    #print(v)
    if G[v] is not None:
        ans += 1
        for w in G[v]:
            que.append(w)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

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

*p, = range(N)
Z = [0]*M
A = X[:]
C = [-1]*N
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
        A[px] += A[py]
    else:
        p[px] = py
        A[py] += A[px]
    return 1

G = [None for i in range(M)]

ans = 0
for i, (y, a, b) in enumerate(E):
    pa = root(a); pb = root(b)
    ca = C[pa]; cb = C[pb]
    if unite(a, b):
        pa = root(a)
        Z[i] = 1
        C[pa] = i
        #print(">", i, pa, pb, A[pa], y)
        if A[pa] < y:
            G[i] = []
            if ca != -1:
                G[i].append(ca)
            if cb != -1:
                G[i].append(cb)
    else:
        if A[pa] < y:
            G[i] = []
            if ca != -1:
                G[i].append(ca)
            C[pa] = i

sx = sum(X)
#print(Z)

if N > 1:
    from collections import deque
    que = deque()
    if sx < E[C[0]][0]:
        que.append(C[0])
    #print(G, C)
    while que:
        v = que.popleft()
        #print(v)
        if G[v] is not None:
            ans += 1
            for w in G[v]:
                que.append(w)
print(ans)
s=sorted(list(input()));a=s.index('1');print(2*min(a,len(s)-a))

### FIXED CODE ###

s=sorted(list(input()))
if s[0]==s[-1]:
  print(0)
else:
  a=s.index('1')
  print(2*min(a,len(s)-a))
a, b = map(int, input().split( ))
s = a + b
if s %2 ==1:
  print('IMPOSSIBLE')
else;
print(s//2)

### FIXED CODE ###

a, b = map(int, input().split( ))
s = a + b
if s %2 ==1:
  print('IMPOSSIBLE')
else:
  print(s//2)