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

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

xsum=max(max(x),a)*n
dp=[[[0]*(xsum+1) for i in range(n+1)] for ii in range(n+1)]

dp[0][0][0]=1

for j in range(1,n+1):
    for k in range(0,n+1):    
        for s in range(0,xsum+1):    
            if s<x[j-1] :
                dp[j][k][s]=dp[j-1][k][s]
            elif s>=x[j-1] and k>=1:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]
            else:
                dp[j][k][s]=0
dsum=0
for k in range(1,n+1):
    dsum=dsum+dp[n][k][k*a]
print(dsum)
    

### FIXED CODE ###

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

for i in range(n):
    x[i]=x[i]-a
    
nx=n*n
dp=[[0]*(2*nx+1) for i in range(n+1)]

#print(dp)

dp[0][nx]=1

for j in range(1,n+1):
    jj=j-1
    for t in range(2*nx+1):
        if t-x[jj]<0 or 2*nx<t-x[jj]:
            dp[j][t]=dp[j-1][t]
        elif 0<t-x[jj] and  t-x[jj]<2*nx:
            dp[j][t]=dp[j-1][t]+dp[j-1][t-x[jj]]
        else:
            dp[j][t]=0

print(dp[n][nx]-1)
### BUGGY CODE ###


class UnionFindByRank():
    def __init__(self, n):
        self.number = n
        self.parents = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 全ての要素の親を求める
    def calc_parents(self):
        self.parents = [self.find(i) for i in self.parents]

    # 根を出力する
    def roots(self):
        self.calc_parents()
        return list(set(self.parents))

    # rootを親として持つ
    def groupcounts(self, root):
        self.calc_parents()
        return self.parents.count(root)


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

for i in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

groups = uf.roots()
counts = [uf.groupcounts(group) for group in groups]
print(max(counts))


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
n,m = map(int, input().split())

uf = UnionFind(n)

for i in range(m):
    a,b = map(int, input().split())
    uf.union(a-1, b-1)
ans = 0
roots = uf.roots()
cnt = []
for r in roots:
    cnt.append(uf.size(r))
cnt.sort(reverse=True)
ans = cnt[0]
print(ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
L=[]
R=[]
for i in range(Q):
    A=list(map(int,input().split()))
    L.append(A[0])
    R.append(A[1])
def X(l,r):
    c=0
    T=S[l-1:r]
    for i in range(r-l):
        if T[i]=="A" and T[i+1]=="C":
            c+=1
    print(c)
for k in range(Q):
    X(L[k],R[k])

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
L=[]
R=[]
C=[0]*N
c=0
for i in range(Q):
    A=list(map(int,input().split()))
    L.append(A[0])
    R.append(A[1])
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        c+=1
        C[i]=c
    else:
        C[i]=c
C[N-1]=c
S+="X"
for i in range(Q):
    p=0
    if S[R[i]-1]=="A" and S[R[i]]=="C":
        p=C[R[i]-1]-C[L[i]-1]-1
    else:
        p=C[R[i]-1]-C[L[i]-1]
    if S[L[i]-1]=="A" and S[L[i]]=="C":
        p+=1
    print(p)
### BUGGY CODE ###

def main():
    from bisect import bisect_left as bs

    n, m, *abc = map(int, open(0).read().split())
    a = sorted(abc[:n])
    *bc, = zip(*[iter(abc[n:])] * 2)

    for b, c in bc:
        i = bs(a, c)
        a = a[:i] + [c] * b + a[i:]

    print(sum(a[-n:]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    n, m, *abc = map(int, open(0).read().split())
    a = Counter(abc[:n])
    bc = abc[n:]
    for i, j in zip(*[iter(bc)] * 2):
        a[j] += i

    cnt = n
    ans = 0
    keys = list(a.keys())
    keys.sort(reverse=True)

    for k in keys:
        m = a[k]
        if m <= cnt:
            ans += k * m
            cnt -= m
        else:
            ans += k * cnt
            break

    print(ans)


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

n,q=map(int,input().split())
s=list(input())
l=[]
for _ in range(q):
    l.append(map(int,input().split()))

for i,j in l:
    ans=0
    for k in range(i-1,j-1):
        if s[k]=="A" and s[k+1]=="C":
            ans+=1
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

import heapq
n,m=map(int,input().split())
c=[list(map(int,input().split())) for i in range(n)]
l=list()
v=0
heapq.heapify(l)
for i in range(1,m+1):
  for j in range(n):
    if c[j][0]==i:
      heapq.heappush(l,(-1)*c[j][1])
  if l:
    v+=heapq.heappop(l)*(-1)
print(v)


### FIXED CODE ###

import heapq
n,m=map(int,input().split())
c=[list(map(int,input().split())) for i in range(n)]
ans, available = 0, []
heapq.heapify(available)
heapq.heapify(c)
for i in range(1, m+1):
    while len(c)!=0 and c[0][0]<=i:
        now = heapq.heappop(c)
        heapq.heappush(available,-now[1])
    if len(available) != 0:
        ans -= heapq.heappop(available)
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7

ans = 0

def com(n, r):
  r = min(r, n - r)
  numer = reduce(mul, range(n, n - r, -1), 1)
  denom = reduce(mul, range(1, r + 1), 1)
  return numer // denom

start = com(N - 1, K - 1)
x = N - 1

for i in range(N):
  if N - 1 - i >= K - 1:
    ans -= A[i] * com(N - 1 - i, K - 1)
    ans += A[- i - 1] * com(N - 1 - i, K - 1)
    ans = ans % MOD
    
    
print(ans % MOD)

### FIXED CODE ###

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7

ans = 0

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

N2 = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N2 + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

#print(cmb(n, r, p))
for i in range(len(A)):
  if N - 1 - i >= K - 1:
    ans += (A[- i - 1] - A[i]) * cmb(N - 1 - i, K - 1, MOD)
    ans = ans % MOD
    
    
print(ans % MOD)
### BUGGY CODE ###

a, b = [int(i) for i in input().split()]

map = [0 for i in range(40)]

for n in range(a, b+1):
    n_str = format(n, "040b")
    for i in range(len(n_str)):
        map[i] ^= int(n_str[i])
ans = 0
map.reverse()
for i in range(len(n_str)):
    ans += (2**i) * map[i]

print(ans)




### FIXED CODE ###

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

# n までに2**(i-1)が何個含まれるか

def solve(n, i):
    res = 0
    mod = 2**i
    c = n // mod
    res += c*mod//2
    if n % mod >= mod//2:
        res += (n%mod - mod//2 + 1)
    return res

b_list = [0]*40
a_list = [0]*40
ans = 0
for i in range(1, 41):
    num_l = solve(b, i)
    num_r = solve(a-1, i)
    num_one = num_l - num_r
    if num_one% 2 == 1:
        ans += 2**(i-1)
print(ans)
### BUGGY CODE ###

import numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()
#     s = s.replace(".", "0").replace("#", "1")
#     s = list(map(int, list(s)))
    ss.append(s)
# ss = np.array(ss)
    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.pop()
        if (now_h, now_w) in que:
            continue
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h][next_w] == "#":
                continue
            a = dp[now_h, now_w] + 1
            if dp[next_h, next_w] > a:
                dp[next_h, next_w] = a
                que.append((next_h, next_w))
    score = np.max(dp[dp != 9999])
    return score

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh][sw] == ".":
            score = find(sh, sw)
            if maximum < score:
                maximum = score

print(maximum)

### FIXED CODE ###

import numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()
#     s = s.replace(".", "0").replace("#", "1")
#     s = list(map(int, list(s)))
    ss.append(s)
# ss = np.array(ss)
    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.popleft()
        if (now_h, now_w) in que:
            continue
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h][next_w] == "#":
                continue
            a = dp[now_h, now_w] + 1
            if dp[next_h, next_w] > a:
                dp[next_h, next_w] = a
                que.append((next_h, next_w))
#             print(que)
    score = np.max(dp[dp != 9999])
    return score

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh][sw] == ".":
            if sh > 0 and sh < h - 1 and sw > 0 and sw < w - 1:
                if 0 + (ss[sh + 1][sw] == ".") + (ss[sh - 1][sw] == ".") + (ss[sh][sw + 1] == ".") + (ss[sh][sw - 1] == ".") >= 3:
                    continue
            score = find(sh, sw)
            if maximum < score:
                maximum = score

print(maximum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    g = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]
    data = [list(map(int, input().split())) for _ in range(M)]


    for a, b, _ in data:
        g[b].append(a)
        g2[a].append(b)

    visit = [False]*(N+1)
    visit2 = [False]*(N+1)

    queue = [N]
    while len(queue) > 0:
        nextqueue = []
        for now in queue:
            visit[now] = True
            for next in g[now]:
                if not visit[next]:
                    nextqueue.append(next)
        queue = nextqueue[:]

    queue = [1]
    while len(queue) > 0:
        nextqueue = []
        for now in queue:
            visit2[now] = True
            for next in g2[now]:
                if not visit2[next]:
                    nextqueue.append(next)
        queue = nextqueue[:]




    for i in range(1, N+1):
        visit[i] = visit[i] and visit2[i]


    INF = -1000000001
    d = [INF] * (N+1)
    d[1] = 0

    for i in range(N):
        d_N = [d[i] for i in range(1, N+1) if visit[i]]
        for j in range(M):

            d[data[j][1]] = max(d[data[j][1]], d[data[j][0]]+data[j][2]-P)
        if i == N-1:
            if d_N != [d[i] for i in range(1, N+1) if visit[i]]:
                ans = -1

            else:
                ans = d[N]

    if ans == -1:
        print(-1)
    else:
        print(max(0, ans))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import queue
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    g = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]
    data = [list(map(int, input().split())) for _ in range(M)]
    for a, b, _ in data:
        g2[b].append(a)
        g[a].append(b)

    visit = [False]*(N+1)
    visit2 = [False]*(N+1)

    q = queue.Queue()
    q.put(1)
    visit[1] = True
    while (not q.empty()):
        now = q.get()
        for next in g[now]:
            if not visit[next]:
                visit[next] = True
                q.put(next)

    q = queue.Queue()
    q.put(N)
    visit2[N] = True
    while (not q.empty()):
        now = q.get()
        for next in g2[now]:
            if not visit2[next]:
                visit2[next] = True
                q.put(next)

    for i in range(1, N+1):
        visit[i] = visit[i] and visit2[i]


    INF = 1000000001
    d = [(-1)*INF for i in range(N+1)]
    d[1] = 0

    for i in range(N):
        d_N = [d[i] for i in range(1, N+1) if visit[i]]
        for j in range(M):
            a = data[j][0]
            b = data[j][1]
            c = data[j][2]
            d[b] = max(d[b], d[a]+c-P)
        if i == N-1:
            if d_N != [d[i] for i in range(1, N+1) if visit[i]]:
                ans = -1

            else:
                ans = d[N]

    if ans == -1:
        print(-1)
    else:
        print(max(0, ans))

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

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

res=[0]*(n-k+1)
for i in range(n-k+1):
    x = 1
    for j in A[i:k+i]:
        x *= j
    res[i]=x
for i in range(1,len(res)):
    if res[i] > res[i-1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

for i in range(n-k):
    if A[k+i] > A[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

def main():
  AC = 0
  WA = 0
  
  N,M = map(int, input().split())
  
  Q = [0] * N
  
  P = [0] * M
  S = [0] * M
  
  for i in range(M):
    _p, _s = input().split()
    P[i] = int(_p)
    S[i] = _s
    
  for i,s in enumerate(S):
    if s == 'AC':
      if Q[P[i]-1]  == 0:
        AC += 1
        for j in range(i):
          if P[j] == P[i] and S[j] == 'WA':
          	WA += 1
        Q[P[i]-1]  = 1
  
  print(AC, WA)
  return 0

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  AC = 0
  WA = 0
  
  solving = {}
  solved = {}
  
  N,M = map(int, input().split())
  
  for i in range(M):
    p, s = input().split()
    if p in solved:
      continue
    elif s == 'WA':
      if p in solving:
        _wa = solving[p]
        solving[p] = _wa + 1
      else:
        solving[p] = 1
    else:
      AC += 1
      if p in solving:
      	WA += solving[p]
      solved[p] = True
  
  print(AC, WA)
  return 0
 
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

n,q = map(int, input().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(n-1)]
p_x = [list(map(int, sys.stdin.readline().split())) for _ in range(q)]

v = [[] for i in range(n)]
for e in a_b:
    v[e[0]-1]+=[e[1]-1]
    v[e[1]-1]+=[e[0]-1]
score = [0 for i in range(n)]
for e in p_x:
    score[e[0]-1]+=e[1]

def dfs(p):
    for c in v[p]:
        if not c in visited:
            visited.append(c)
            score[c]+=score[p]
            if len(visited)==n:
                print(*score)
            else:
                dfs(c)
visited = [0]                
dfs(0)

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(1000000)

n,q = map(int, input().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(n-1)]
p_x = [list(map(int, sys.stdin.readline().split())) for _ in range(q)]

v = [deque([]) for i in range(n)]
for e in a_b:
    v[e[0]-1]+=[e[1]-1]
    v[e[1]-1]+=[e[0]-1]
score = [0 for i in range(n)]
for e in p_x:
    score[e[0]-1]+=e[1]
def dfs(p, bp=-1):
    while v[p]:
        c =v[p].popleft()
        if c ==bp:
            continue
        #print(p, c, bp)
        score[c]+=score[p]
        dfs(c, bp=p)
visited = [0]                
dfs(0)
print(*score)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
l = []
for a in A:
  l.append(a)
  l = l[::-1]
print(*l)

### FIXED CODE ###

from collections import deque
n = int(input())
A = list(map(int,input().split()))
l = deque()
for i in range(len(A)):
  if n % 2 == 0:
    if i % 2 == 0:
      l.append(A[i])
    else:
      l.appendleft(A[i])
  else:
    if i % 2 == 0:
      l.appendleft(A[i])
    else:
      l.append(A[i])
print(*l)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
l = []
r = []
for i in range(q):
    li,ri = map(int,input().split())
    l.append(li)
    r.append(ri)
  
al = [0]*n  
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        al[i] = 1
        
for j in range(q):
    left = l[j]
    right = r[j]
    print(sum(al[left-1:right-1]))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
l = []
r = []
for i in range(q):
    li,ri = map(int,input().split())
    l.append(li)
    r.append(ri)
  
al = [0]*n
for i in range(1,n):
    if s[i-1] == "A" and s[i] == "C":
        al[i] = al[i-1] + 1
    else:
        al[i] = al[i-1]
        
for j in range(q):
    left = l[j]-1
    right = r[j]-1
    print(al[right]-al[left])
### BUGGY CODE ###

N = int(input())
P = list(map(float, input().split()))
memo = [[0 for j in range(N+1)] for i in range(N)]

memo[0][0] = 1 - P[0]
memo[0][1] = P[0]

for i in range(1, N):
    memo[i][0] = memo[i-1][0] * (1 - P[i])
    for j in range(1, i+2):
        memo[i][j] = memo[i-1][j-1] * P[i]
        memo[i][j] += memo[i-1][j] * (1 - P[i])
            
print(sum(memo[-1][N//2+1:]))


### FIXED CODE ###

N = int(input())
P = list(map(float, input().split()))
memo = [[0 for j in range(N+1)] for i in range(N)]

memo[0][0] = 1 - P[0]
memo[0][1] = P[0]

for i in range(1, N):
    memo[i][0] = memo[i-1][0] * (1 - P[i])
    for j in range(1, i+2):
        memo[i][j] = memo[i-1][j-1] * P[i]
        memo[i][j] += memo[i-1][j] * (1 - P[i])
            
print(sum(memo[-1][N//2+1:]))
### BUGGY CODE ###

s = input()
l = list(s)
cnt = 0
for i in range(len(l)):
    if l[i] == "W":
        cnt += l[:i].count("B")
print(cnt)

### FIXED CODE ###

s=input()
b=0
cnt=0
for i in range(len(s)):
  if s[i]=="B":
    b+=1
    cnt+=i
print(int((len(s)*2-b-1)*b*(1/2)-cnt))
### BUGGY CODE ###

R,G,B,N= map(int,input().split())

cnt = 0
for i in range(N+1):
    for j in range(N+1):
        k = N - R*i- G*j
        if k<0 or k % B != 0 : continue
        k /= B
        cnt += 1
            
print(cnt)

### FIXED CODE ###

R,G,B,N= map(int,input().split())

cnt = 0
for i in range(N+1):
    for j in range(N+1):
        k = N - R*i- G*j
        if k<0 or k % B != 0 : continue
        cnt += 1
            
print(cnt)
### BUGGY CODE ###

n= int(input())
s = str(input())

r = []
g = []
b = []
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif(s[i]=="G"):
        g.append(i)
    elif(s[i]=="B"):
        b.append(i)
score = len(r)*len(g)*len(b)
for i in r:
    for j in g:
        dist=abs(j-i)
        if (i>j):
            bi = i+dist
            if bi in b:
                score -=1
            bi = j-dist
            if bi in b:
                score -=1
        else:
            bi = j+dist
            if bi in b:
                score-=1
            bi = i-dist
            if bi in b:
                score-=1
        if((i+j)%2==0 and (i+j)/2 in b):
            score-=1
# print(count_)
print(score)

### FIXED CODE ###

n= int(input())
s = str(input())

r=set()
g=set()
b=set()
for i in range(n):
    if s[i]=='R':
        r.add(i)
    if s[i]=='G':
        g.add(i)
    if s[i]=='B':
        b.add(i)
score = len(r)*len(g)*len(b)
for i in r:
    for j in g:
        dist=abs(j-i)
        if (i>j):
            bi = i+dist
            if bi in b:
                score -=1
            bi = j-dist
            if bi in b:
                score -=1
        else:
            bi = j+dist
            if bi in b:
                score-=1
            bi = i-dist
            if bi in b:
                score-=1
        if((i+j)%2==0 and (i+j)/2 in b):
            score-=1
# print(count_)
print(score)
### BUGGY CODE ###

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
import bisect
import math
cnt=0
for i in range(n):
    if h[i]<=0:
        continue
    else:
        m=math.ceil(h[i]/a)
        cnt+=m
        k=bisect.bisect_right(x,x[i]+2*d,lo=i)
        for j in range(i,k):
            h[j]-=(m*a)
print(cnt)


### FIXED CODE ###

import bisect
import math
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
g=[0]*n
cnt=0
for i in range(n):
    #print(h)
    if h[i]>0:
        m=math.ceil(h[i]/a)
        cnt+=m
        k=bisect.bisect_right(x,x[i]+2*d,lo=i)
        if i!=n-1:
            h[i]-=m*a
            g[i]-=m*a
            if k<n:
                g[k]+=m*a
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
    else:
        if i!=n-1:
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
print(cnt)
### BUGGY CODE ###

import collections

n,m = map(int,input().split())
friend = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    friend[a].append(b)
    friend[b].append(a)


q = collections.deque()
visited = [0 for i in range(n)]

ans = 0
for i in range(n):
    if visited[i] == 0:
        visited[i] = 1
        tmp = 1
        for j in friend[i]:
            if visited[j] == 0:
                visited[j] = 1
                tmp += 1
                q.append(j)
        while q:
            s = q.pop()
            for k in friend[s]:
                if visited[k] == 0:
                    tmp += 1
                    q.append(k)
    ans = max(ans,tmp)

print(ans)

### FIXED CODE ###

import collections

n,m = map(int,input().split())
friend = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    friend[a].append(b)
    friend[b].append(a)

q = collections.deque()
visited = [0 for i in range(n)]

ans = 0
for i in range(n):
    tmp = 0
    if visited[i] == 0:
        visited[i] = 1
        tmp += 1
        for j in friend[i]:
            if visited[j] == 0:
                visited[j] = 1
                tmp += 1
                q.append(j)
        while q:
            s = q.pop()
            for k in friend[s]:
                if visited[k] == 0:
                    visited[k] = 1
                    tmp += 1
                    q.append(k)
    ans = max(ans,tmp)

print(max(ans,1))
### BUGGY CODE ###

N = int(input())
A = [int(s) for s in input().split()]
mod = 10**9+7

ans  = 0
for i in range(N-1):
    seki = A[i]*sum(A[i+1:])
    ans += seki

print(int(ans%mod))

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]
mod = 10**9+7

wa = 0
wa_list = []
for i in range(N)[::-1]:
    if i == 0:
        break
    wa += A[i]
    wa_list.append(wa)

wa_list.reverse()
ans  = 0
for i in range(N-1):
    seki = A[i]*wa_list[i]
    ans += seki

print(ans % mod)