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

def inpl():
    return list(map(int, input().split()))


N, K = inpl()
A = inpl()

if K == 0:
    print(sum(A))
    exit()

t = len(bin(K)) - 2
oneCounter = [0 for _ in range(t)]
# print(t)
sumA = 0
for a in A:
    sumA += a
    tmp = bin(a)[2:]
    # print(tmp)
    for i, x in enumerate(reversed(tmp)):
        # print(i, x)
        if i >= t:
            break
        elif x == "0":
            continue
        oneCounter[i] += 1
    # print(a, zeroCounter)

# print(oneCounter)
nibeki = [2 ** i for i in range(t)]
ans = sumA
for i in range(t - 1):
    if 2 * oneCounter[i] < N:
        # print(i, oneCounter[i])
        ans += nibeki[i] * (N - 2*oneCounter[i])

# print(ans, "koo")
for i in range(nibeki[t-1], K+1):
    tmp = 0
    # print(bin(i))
    for j in range(t):
        # print(j)
        if bin(i)[-1 - j] == "0":
            # print(j, "i")
            continue
        tmp += nibeki[j] * (N-2*oneCounter[j])
    # print(i, tmp)
    ans = max(ans, sumA + tmp)
print(ans)


### FIXED CODE ###

def inpl():
    return list(map(int, input().split()))


N, K = inpl()
A = inpl()

if K == 0:
    print(sum(A))
    exit()

t = len(bin(K)) - 2
oneCounter = [0 for _ in range(t)]
# print(t)
sumA = 0
for a in A:
    sumA += a
    tmp = bin(a)[2:]
    # print(tmp)
    for i, x in enumerate(reversed(tmp)):
        # print(i, x)
        if i >= t:
            break
        elif x == "0":
            continue
        oneCounter[i] += 1
    # print(a, zeroCounter)

# print(oneCounter)
nibeki = [2**i for i in range(t)]
ans = sumA
orK = bin(K)[2:]
# print(orK)
tmp = 0
for j in range(len(orK)):
    if orK[j] == "0":
        continue
    tmp += nibeki[t - 1 - j] * (N - 2 * oneCounter[t - 1 - j])
ans = max(ans, sumA + tmp)

for i in range(len(orK)):
    if orK[i] == "0":
        continue

    tmp = 0
    for j in range(i):
        if orK[j] == "0":
            continue
        tmp += nibeki[t - 1 - j] * (N - 2 * oneCounter[t - 1 - j])
    # print(tmp)

    for j in range(i + 1, t):
        if 2 * oneCounter[t - 1 - j] < N:
            # print(i, oneCounter[i])
            tmp += nibeki[t - 1 - j] * (N - 2 * oneCounter[t - 1 - j])
    # print(orK, i, ans, tmp)
    ans = max(ans, sumA + tmp)
print(ans)
### BUGGY CODE ###

# coding: utf-8
n = int(input())
P = [int(x) for x in input().split(" ")]

def check(i):
    flag = True
    for j in range(i):
        if P[j] < P[i-1]:
            flag = False
            break
    if flag:
        return 1
    else:
        return 0
ans = 0
for i in range(1,n+1):
    ans += check(i)
print(ans)

### FIXED CODE ###

# coding: utf-8
n = int(input())
P = [int(x) for x in input().split(" ")]
mx = P[0]
ans = 1
for i in range(1,n):
    if mx > P[i]:
        ans += 1
        mx = P[i]
print(ans)
### BUGGY CODE ###

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

money = 0
count = 0
while count < M:
    min_ = 1000000000
    index = 0
    for i in range(len(A_B)):
        if A_B[i][0] < min_:
            min_ = A_B[i][0]
            index = i
    if count+A_B[index][1] <= M:
        count += A_B[index][1]
        money += A_B[index][0] * A_B[index][1]
    else:
        money += A_B[index][0] * (M-count)
        count = M
    A_B.pop(index)
print(money)


### FIXED CODE ###

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

money = 0
count = 0
A_B = sorted(A_B)
while count < M:
    if count+A_B[0][1] <= M:
        count += A_B[0][1]
        money += A_B[0][0] * A_B[0][1]
    else:
        money += A_B[0][0] * (M-count)
        count = M
    A_B.pop(0)
print(money)
### BUGGY CODE ###

S = list(input())

MOD = 10 ** 9 + 7

dp = [[0 for i in range(13)] for i in range(10**5+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] != "?":
        for j in range(13):
            dp[i+1][(j * 10 + int(S[i])) % 13] += dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                dp[i+1][(j * 10 + k) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[len(S)][5])

### FIXED CODE ###

S = list(input())

MOD = 10 ** 9 + 7

dp = [[0 for i in range(13)] for i in range(10**5+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] != "?":
        for j in range(13):
            dp[i+1][(j * 10 + int(S[i])) % 13] += dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                dp[i+1][(j * 10 + k) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[len(S)][5])
### BUGGY CODE ###

N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ (lambda a,b:[min(a,b),max(a,b)])(*[int(it)-1 for it in input().split()]) for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

#print (N,M,pli,sli)
#print (ue)
#print (dw)
for a,b in sli:
  if ( b == ue[a] or a == ue[b] ):
    continue
  if (1==1):
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if (_a == _b and _a != -1):
      continue

    assert( ue[_a]==-1 )
    assert( ue[_b]==-1 )
      
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a

s = 0
for i in range(N):
  if ue[i]==-1:
    ue[i]=i 
for i in range(N):
  if (ue[i]==ue[pli[i]]):
    s+=1
print (s)

### FIXED CODE ###

N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ [int(it)-1 for it in input().split()] for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

for a,b in sli:
  if ( b == ue[a] or a == ue[b] ):
    continue
  else:
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if (_a == _b and _a != -1):
      continue
    if (len(dw[_a]) < len(dw[_b])):
      _a,_b=_b,_a
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a

s = 0
for i in range(N):
  if ue[i]==-1:
    ue[i]=i 
for i in range(N):
  if (ue[i]==ue[pli[i]]):
    s+=1
print (s)
### BUGGY CODE ###

import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()
cnt = 0
for i in range(n):
    for j in range(bisect.bisect_right(b, a[i]), n):
        cnt += n - bisect.bisect_right(c, b[j])

print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()
cnt = 0
for i in range(n):
    cnt += bisect.bisect_left(a, b[i]) * (n - bisect.bisect(c, b[i]))

print(cnt)
### BUGGY CODE ###

s=input()
n=int(input())
strlist=[input() for i in range(n)]
for i in range(n):
  if strlist[i][0]=='1':
    s=s[::-1]
  elif strlist[i][0]=='2' and strlist[i][2] == '1':
    s = '{}{}'.format(strlist[i][4],s)
  elif strlist[i][0]=='2' and strlist[i][2] == '2':
    s = '{}{}'.format(s,strlist[i][4])
print(s)

### FIXED CODE ###

from collections import deque
s=deque(input())
n=int(input())
r=0
for i in range(n):
    strlist=input()
    if strlist[0]=='1':
        r+=1
    elif strlist[0]=='2' and strlist[2] == '1':
        if r%2==0:
            s.appendleft(strlist[4])
        else:
            s.append(strlist[4])
    elif strlist[0]=='2' and strlist[2] =='2':
        if r%2==0:
            s.append(strlist[4])
        else:
            s.appendleft(strlist[4])
if r%2==0:
    for s_ in s:
        print(s_, end='')
else:
    s.reverse()
    for s_ in s:
        print(s_, end='')
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())

#seg_tree
def init(n, s):
    num = len(str(bin(n-1))) -2
    seg = [set() for _ in  range(2**(num+1))]
    seg_num = 2**num

    for i in range(n):
        seg[i + seg_num] = set(s[i])

    for i in range(seg_num-1, 0, -1):
        seg[i] = (seg[i*2] | seg[i*2+1])

    return seg, seg_num

def calc_sum(head, tail):
    head += seg_num
    tail += seg_num
    l = []
    while(head <= tail):
        if(head == tail):
            l.append(head)
            break

        if(head % 2 == 1):
            l.append(head)
            head += 1
        head = head //2

        if(tail % 2 == 0):
            l.append(tail)
            tail -= 1
        tail = tail //2

    ans = set()
    for i in l:
        ans = (ans | seg[i])
    ans = len(ans)
    return(ans)

def update(i,s):
    i += seg_num
    seg[i] = {s}
    while(i > 1):
        i = i//2
        seg[i] = (seg[2*i] | seg[2*i+1])

seg,seg_num = init(n,s)

for i in range(q):
    q1,q2,q3 = input().split()
    if(q1 =='1'):
        update(int(q2)-1, q3)
    else:
        q2,q3 = int(q2),int(q3)
        print(calc_sum(q2-1, q3-1))

### FIXED CODE ###

n = int(input())
s = input()
q = int(input())

#seg_tree
def init(n, s):
    num = len(str(bin(n-1))) -2
    seg = [0] * (2**(num+1))
    seg_num = 2**num

    for i in range(n):
        tmp = ord(s[i]) - 97
        seg[i + seg_num] = 1 << tmp

    for i in range(seg_num-1, 0, -1):
        seg[i] = seg[i*2] | seg[i*2+1]

    return seg, seg_num

def calc_sum(head, tail):
    head += seg_num
    tail += seg_num
    l = []
    while(head <= tail):
        if(head == tail):
            l.append(head)
            break

        if(head % 2 == 1):
            l.append(head)
            head += 1
        head = head //2

        if(tail % 2 == 0):
            l.append(tail)
            tail -= 1
        tail = tail //2

    ans = 0
    for i in l:
        ans = ans | seg[i]
    ans = str(bin(ans)).count('1')
    return(ans)

def update(i,s):
    i += seg_num
    tmp = ord(s) - 97
    seg[i] = 1 << tmp
    while(i > 1):
        i = i//2
        seg[i] = seg[2*i] | seg[2*i+1]

seg,seg_num = init(n,s)

for i in range(q):
    q1,q2,q3 = input().split()
    if(q1 =='1'):
        update(int(q2)-1, q3)
    else:
        q2,q3 = int(q2),int(q3)
        print(calc_sum(q2-1, q3-1))
### BUGGY CODE ###

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : uからvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        for j in range(n):
            if d[j] > d[v]+cost[v][j]: # vを使った場合と使わない場合の最短値で比較
                d[j] = d[v]+cost[v][j]

    return d

n = int(input())
cost = [[float('inf') for i in range(n)] for j in range(n)]

for _ in range(n-1):
    a, b, c = map(int, input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

q, k = map(int, input().split())

d = dijkstra(k-1,n,n-1,cost)

ans = [0]*q

for i in range(q):
    x, y = map(int, input().split())
    ans[i] = d[x-1]+d[y-1]

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



### FIXED CODE ###

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

n = int(input())
from collections import defaultdict
abc = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b,c in abc:
    a,b = a-1,b-1
    es[a].append((b,c))
    es[b].append((a,c))

q, k = map(int, input().split())
xy = [tuple(map(int,input().split())) for i in range(q)]

dist = [-1]*n

def dfs(v=0,parent=-1,d=0):
    for next_v,dd in es[v]:
        if dist[next_v] == -1:
            dist[next_v] = d + dd
            dfs(next_v,v,dist[next_v])

dist[k-1] =0
dfs(k-1,-1,0)
ans=[]
for x,y in xy:
    x,y=x-1,y-1
    ans.append(dist[x]+dist[y])

print(*ans,sep='\n')
### BUGGY CODE ###


import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()

def resolve():
    R, C, K = map(int, inpS().split())
    G = [[0] * (C + 1) for _ in range(R + 1)]
    for _ in range(K):
        r, c, v = map(int, inpS().split())
        G[r][c] = v

    dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                # 次の行に移動する場合
                if i + 1 <= R:
                    # 移動先のアイテムを取らない場合
                    dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][k])
                    # 移動先のアイテムを取る場合
                    dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j][k] + G[i + 1][j])
                # 次の列に移動する場合
                if j + 1 <= C:
                    # 移動先のアイテムを取らない場合
                    dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])
                    # 現在のkが3未満のときのみ, 移動先のアイテムを取ることが可能
                    if k < 3:
                        dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k] + G[i][j + 1])

    ans = 0
    for k in range(4):
        ans = max(ans, dp[-1][-1][k])
    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###


def resolve():
    R, C, K = map(int, input().split())
    G = [[0] * (C+1) for _ in range(R+1)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r][c] = v

    DP1 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で1個以下とったという条件のもとの最大
    DP2 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で2個以下とったという条件のもとの最大
    DP3 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で3個以下とったという条件のもとの最大

    for r in range(1, R+1):
        for c in range(1, C+1):
            # 更新の順番に注意
            # mid = max(DP1[c], DP2[c], DP3[c]) + I[r][c]
            mid = DP3[c] + G[r][c]
            DP3[c] = max(DP3[c - 1], mid, DP2[c - 1] + G[r][c])  # 3個
            DP2[c] = max(DP2[c - 1], mid, DP1[c - 1] + G[r][c])  # 2個
            DP1[c] = max(DP1[c - 1], mid)  # 1個

    print(DP3[C])

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

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

inf = 10 ** 9
max_h = 2 * 10**4 + 10
dp = [inf] * max_h
dp[0] = 0
for a, b in ab:
    for i in range(max_h - a + 1):
        dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[h:]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

inf = 10 ** 9
max_h = 2 * 10**4 + 10
dp = [inf] * max_h
dp[0] = 0
for a, b in ab:
    for i in range(max_h - a + 1):
        dp[i] = min(dp[i], dp[i - a] + b)

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

n = int(input())
factors = []
while n%2 == 0:
    factors.append(2)
    n //=2

for f in range(3, int(n**0.5)+ 1, 2):
    while n%f == 0:
        factors.append(f)
        n //= f
if n != 1:
    factors.append(n)

nf = len(factors)

fab = 11
sset = set()
als = 2**nf
for i in range(als):
    if als^i in sset:
        continue
    sset.add(i)
    
    a = 1
    b = 1
    for j in range(nf):
        if (i>>j)&1:
            a *= factors[j]
        else:
            b *= factors[j]

    fab = min(fab, max(len(str(a)), len(str(b))))
print(fab)


### FIXED CODE ###

n = int(input())
factors = []
while n%2 == 0:
    factors.append(2)
    n //=2

for f in range(3, int(n**0.5)+ 1, 2):
    while n%f == 0:
        factors.append(f)
        n //= f
if n != 1:
    factors.append(n)

nf = len(factors)

fab = 11
sset = set()
als = 2**nf
for i in range(als):
    if als^i in sset:
        continue
    sset.add(i)
    a = 1
    b = 1
    for j in range(nf):
        if (i>>j)&1:
            a *= factors[j]
        else:
            b *= factors[j]

    fab = min(fab, max(len(str(a)), len(str(b))))
print(fab)
### BUGGY CODE ###

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.append([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)


### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)
### BUGGY CODE ###

import sys

default_x = 0
default_y = 0

n = int(input())

a = []

#標準入力をN分読み込み
for i in range(n):
        a.append(list(map(int,input().split())))

times = 0
for i in range(n):
    for j in range(a[i][0]+times):
        if default_x < a[i][1]:
            default_x += 1
        elif default_x > a[i][1]:
            default_x -= 1

        elif default_y < a[i][2]:
            default_y += 1
        elif default_y > a[i][2]:
            default_y -= 1
        else:
            default_y -= 1

    if default_x != a[i][1] or default_y != a[i][2]:
        print('No')
        sys.exit()

    times  = a[i][0]

print('Yes')

### FIXED CODE ###

n = int(input())

travel = list()
#start point
travel.append((0,0,0))

for i in range(n):
  travel.append(tuple(map(int,input().split())))


for j in range(n):
  dist = abs(travel[j][0]-travel[j+1][0])

  dd = abs(travel[j][1]-travel[j+1][1])+abs(travel[j][2]-travel[j+1][2])
  
#fail
  if dist < dd or (dd%2 != dist%2):
    print("No")
    exit(0) 

print("Yes")
### BUGGY CODE ###

import math
n=int(input())
if n==2:
    print(n)
else:
    cost=0
    for i in range(n,10**6):
        for j in range(2,int(math.sqrt(i))+1):
            if i%j==0:
                cost+=1
        if cost==0:
            print(i)
            break


### FIXED CODE ###

n=int(input())
for i in range(n,10**6):
  for j in range(2,int(i**0.5)+1):
    if i%j==0:
      break
  else:
    print(i)
    break
### BUGGY CODE ###

import functools
import operator
n = int(input())
a = list(map(int, input().split()))
result = functools.reduce(operator.mul, a)
if result > (10**18):
    print("-1")
else:
    print(result)

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    if 0 in a:
        print(0)
        return
    prod = 1
    for i in a:
        prod *= i
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)
main()
### BUGGY CODE ###

from itertools import chain

n, m = map(int, input().split())
H = list(map(int, input().split()))

ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))

count = 0
skipset = []

for i in range(1, n+1):
    if i in skipset:
        continue
    f = {i}
    c= []
    e= []
    for j in ab:
        if i in j:
            c.append(j)
    d =set(chain.from_iterable(c)) -f
    #print(d)

    for k in d:
        e.append(H[k-1])



    if len(e)==0:
        count += 1
        #print('Yes')

        continue
    elif max(e) < H[i-1]:
        #print(i, H[i - 1], max(e))
        skipset.append(d)
        count += 1
        #print('Yes')
    else:

        pass

print(count)

### FIXED CODE ###

N, M = map(int, input().split())
c_list = [[] for _ in range(N)]
e_list = list(map(int, input().split()))
for _ in range(M):
   a, b = map(lambda i: int(i) - 1, input().split())
   c_list[a].append(b)
   c_list[b].append(a)
ans = 0
for i, e in enumerate(e_list):
   for j in c_list[i]:
       if e <= e_list[j]:
           break
   else:
       ans += 1

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

h,n = map(int,input().split())

a_li = [0]*n
b_li = [0]*n

for i in range(n):
    a_li[i],b_li[i] = map(int,input().split())
#もらうdp
dp =[10**10]*(h+1)
dp[-1]=0
for i in range(h,-1,-1):
    for j in range(n):
        if i-a_li[j]<=0:
            d=0
        else:
            d=i-a_li[j]
        dp[d]=min(dp[d],dp[i]+b_li[j])
print(dp[0])


    

### FIXED CODE ###

h,n = map(int,input().split())

ab_input = [list(map(int,input().split())) for i in range(n)]
max_d = max(a for a,b in ab_input)
#配るdp
dp =[0]*(h+max_d)
for i in range(1,h+max_d):
    dp[i]=min(dp[i-a]+b for a,b in ab_input)
print(dp[h])
### BUGGY CODE ###

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

for i in range(1, n+1):
    print(a.count(i))


### FIXED CODE ###

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

ans = [0] * n

for i in lst:
    ans[i-1] += 1

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

n,k=map(int,input().split())
a=[]
dic={}
for i in range(n):
    A,B=map(int,input().split())
    if A in a:
        dic[A]+=B
    else:
        a.append(A)
        dic[A]=B
a=sorted(a)
sum=0
for i in range(len(a)):
    sum+=dic[a[i]]
    if sum>=k:
        print(a[i])
        exit()


### FIXED CODE ###

n,k=map(int,input().split())
list=[0]*(10**5+1)
for i in range(n):
    a,b=map(int,input().split())
    list[a]+=b
sum=0
for l in range(1,len(list)):
    sum+=list[l]
    if sum>=k:
        print(l)
        exit()
### BUGGY CODE ###

import heapq

def dijkstra(ad_lst, n, s, t):
    costs = [float('inf') for i in range(n+1)]
    costs[s] = 0
    prevs = [-1 for _ in range(n+1)]
    Q = []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u]:
            alt = costs[u] + c
            if alt < costs[v]:
                heapq.heappush(Q, [alt, v])
                costs[v] = alt

    return costs

n,m,s,t, = map(int, input().split())

route_y = {i: [] for i in range(n+1)}
route_s = {i: [] for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u].append([v,a])
    route_y[v].append([u,a])
    route_s[u].append([v,b])
    route_s[v].append([u,b])

cost_y = dijkstra(route_y, n, s, t)
cost_s = dijkstra(route_s, n, t, s)
cost_ys = [y+s for y, s in zip(cost_y, cost_s)]
inf = float('inf')
result = [inf for _ in range(n+1)]
min_cost = result[-1]
for i in range(n, 0, -1):
    if min_cost > cost_ys[i]:
        min_cost = cost_ys[i]
    result[i] = min_cost
yen = 10**15
for i in range(1, n+1):
    print(yen - result[i])


### FIXED CODE ###

import heapq
from itertools import accumulate
inf = float('inf')

def dijkstra(ad_lst, n, s):
    costs = [inf for i in range(n+1)]
    costs[s], Q = 0, []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u].items():
            if costs[u] + c < costs[v]:
                heapq.heappush(Q, [costs[u] + c, v])
                costs[v] = costs[u] + c

    return costs

n,m,s,t, = map(int, input().split())

route_y = {i: {} for i in range(n+1)}
route_s = {i: {} for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u][v] = a
    route_y[v][u] = a
    route_s[u][v] = b
    route_s[v][u] = b

cost_y = dijkstra(route_y, n, s)
cost_s = dijkstra(route_s, n, t)
result = list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1], min))
yen = 10**15
[print(yen-result[i]) for i in range(n-1, -1, -1)]