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

#!/usr/bin/env python3

def main():
    n = int(input())
    p = [list(map(int, input().split())) for i in range(n)]
    max_p = []
    for i in range(n):
        a, b = p[i][0], p[i][1]
        if len(max_p) == 0:
            max_p.append([a, b])
        if max_p[0][0]**2 + max_p[0][1]**2 < a**2 + b**2:
            max_p.append([a, b])
    ans = 0
    for mp in max_p:
        for i in range(n):
            tmp = abs(mp[0] - p[i][0]) + abs(mp[1] - p[i][1])
            ans = max(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    n = int(input())
    xy = [list(map(int, input().split())) for i in range(n)]
    max_z, max_w, min_z, min_w = -10**20, -10**20, 10**20, 10**20
    ans = 0
    for p in xy:
        max_z, max_w = max(max_z, p[0] + p[1]), max(max_w, p[0] - p[1])
        min_z, min_w = min(min_z, p[0] + p[1]), min(min_w, p[0] - p[1])
    ans = max(max_z - min_z, max_w - min_w)
    print(ans)


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

import sys
sys.setrecursionlimit(10**9)
INF = 110110110
H, W, K = list(map(int, input().split()))
S = [''] * H
for i in range(H):
    S[i] = input()
ans = H * W

for bit in range(2**(H-1)):
    cnt = bin(bit).count('1')
    id = [0] * H
    for i in range(H-1):
        if bit>>i & 1:
            id[i+1] = id[i] + 1
        else:
            id[i+1] = id[i]
    num = [[0] * W for i in range(id[H-1]+1)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '1':
                num[id[i]][j] += 1
    for i in range(id[H-1]+1):
        for j in range(W):
            if num[i][j] > K:
                cnt = INF
    sum = [0] * (id[H-1]+1)
    for j in range(W):
        need = False
        for i in range(id[H-1]+1):
            if sum[i] + num[i][j] > K:
                need = True
        if need:
            cnt += 1
            for i in range(id[H-1]+1):
                sum[i] = num[i][j]
        else:
            for i in range(id[H-1]+1):
                sum[i] += num[i][j]
    ans = min(ans, cnt)

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF = 110110110
H, W, K = list(map(int, input().split()))
S = [''] * H
for i in range(H):
    S[i] = input()
ans = H * W

for bit in range(2**(H-1)):
    cnt = bin(bit).count('1')
    id = [0] * H
    for i in range(H-1):
        if bit>>i & 1:
            id[i+1] = id[i] + 1
        else:
            id[i+1] = id[i]
    num = [[0] * W for i in range(id[H-1]+1)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '1':
                num[id[i]][j] += 1
    for i in range(id[H-1]+1):
        for j in range(W):
            if num[i][j] > K:
                cnt = INF
    sum = [0] * (id[H-1]+1)
    for j in range(W):
        need = False
        for i in range(id[H-1]+1):
            if sum[i] + num[i][j] > K:
                need = True
        if need:
            cnt += 1
            for i in range(id[H-1]+1):
                sum[i] = num[i][j]
        else:
            for i in range(id[H-1]+1):
                sum[i] += num[i][j]
    ans = min(ans, cnt)

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

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

result = 0
for i in range(N):
    for j in range(i,N):
        tmp = A[i]
        for k in A[i+1:j+1]:
            tmp ^= k
        if tmp == sum(A[i:j+1]):
            result += 1

print(result)



### FIXED CODE ###

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

result = 0
Right = 0
tmp = 0
for left in range(N):
    for right in range(Right,N):
        if not (tmp & A[right]):
            tmp += A[right]
            Right = right + 1
        else:
            break
    tmp -= A[left]
    result += Right - left
print(result)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N, Q = LI()
P = [0] * N
V = [[] for _ in range(N)]

w = [0]*N
for i in range(N-1):
    A, B = LI()
    V[A-1].append(B-1)
    V[B-1].append(A-1)
#    AB[i] = LI()
for i in range(Q):
    p, x = LI()
    P[p-1] += x

#print(V)
for i in range(N):
    w[i] += P[i]

#i = int(0)
#for l in V:
#   for j in l:
#        print(i, j)
#        w[j] += w[i]
#        print(w)
#    i +=1
def solve(v,i):
#    print(v,i)
#    print(w)
#    print("#####")
    if not v[i]:
        return
    else:
        for l in v[i]:
            w[l] += w[i]
            v[l].remove(i)
            solve(v,l)
        return
i =int(0)
solve(V,i)

print(" ".join(map(str,w)))


### FIXED CODE ###


N, Q = map(int, input().split())
a = []
p = []
x = [0]*(N)
A = [0]*(N)

for i in range(N-1):
    t=list(map(int,input().split()))
    if t[0]>t[1]:
        swap = t[1]
        t[1] = t[0]
        t[0] =swap
    a.append((int(t[0]),int(t[1])))
for i in range(Q):
    t=list(map(int,input().split()))
    p.append((int(t[0]),int(t[1])))

a =sorted(a, key=lambda x: x[0])
p =sorted(p, key=lambda x: x[0])

#print(a)
for i in range(Q):
    x[p[i][0]-1] += p[i][1]
for i in range(N):
    A[i] = x[i]
for i in range(N-1):
    La = a[i][0]-1
    Lb = a[i][1]-1

    A[Lb] = A[La]+x[Lb]

print(' '.join(map(str, A)))
### BUGGY CODE ###

import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n, q = rm()
s = rr()
cnt_li = [s[:i].count('AC') for i in range(1, n+1)]
for _ in range(q):
    l, r = rm()
    print(cnt_li[r-1] - cnt_li[l-1])













### FIXED CODE ###

import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n, q = rm()
s = rr()
cnt_li = [0]*n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        cnt_li[i+1] += 1
    cnt_li[i+1] += cnt_li[i]
for _ in range(q):
    l, r = rm()
    print(cnt_li[r-1] - cnt_li[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())#slow,行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh, bw = map(int, input().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append([bh - 1,bw - 1])
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[2,2],[1,1],[1,3]]
hmax = max(set(hcnt))#2
wmax = max(set(wcnt))#1
hmaxindex = [ i for i in range(H) if hcnt[i] == hmax]#[0]
wmaxindex = [ i for i in range(W) if wcnt[i] == wmax]#[0,1,2]
#crosspoint has not bomb

for i in hmaxindex:
    for j in wmaxindex:
        if bomb.count([i, j]) == 0:
            print(hmax + wmax)
            sys.exit()
        else:
            continue
#all crosspoint has bomb
print(hmax + wmax - 1)

### FIXED CODE ###


import sys
from collections import Counter

H, W, M = map(int, sys.stdin.readline().rstrip().split())#行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh,bw=map(int,sys.stdin.readline().rstrip().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append((bh - 1,bw - 1))
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax = max(hcnt)#2
wmax = max(wcnt)#1

crs = 0#hmax and wmax crosspoint
for (i, j) in bomb:
    if hcnt[i] == hmax and wcnt[j] == wmax:
        crs += 1
#all crosspoint has bomb
if crs == Counter(hcnt)[hmax] * Counter(wcnt)[wmax]:
    print(hmax + wmax - 1)
#more than one crosspoint has no bomb
else:
    print(hmax + wmax)
### BUGGY CODE ###

import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=np.array(list(map(int,input().split())))
C=np.array(list(map(int,input().split())))

count=0
for i in range (N):
    count_A=np.sum((A)<B[i])
    count_B=np.sum((C)>B[i])
    count+=count_A*count_B
print(count)

### 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()

count=0
for i in range (N):
    count_A=bisect.bisect_left(A,B[i])
    count_B=len(C)-bisect.bisect_right(C,B[i])
    count+=count_A*count_B
print(count)
### BUGGY CODE ###


def gcd(a,b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b 
    return b

k = int(input())
ans = 0
mem = [[[0 for a in range(k+1)]for b in range(k+1)] for c in range(k+1)]
n = k+1
for i in range(1,n):
    for j in range(1,n):
        for k in range(1,n):
            a = max([i,j,k])
            b = min([i,j,k])
            c = sum([i,j,k]) - a - b
            if mem[a][b][c]:
                ans += mem[a][b][c]
            else:
                d = gcd(gcd(k,j),i)
                ans += d
                mem[a][b][c] = d
            # print("aaaaaa",i,j,k,ans)
print(ans)


### FIXED CODE ###

def gcd(a,b):
    if a < b:
        a, b = b, a
    if mem[a][b]:
        return mem[a][b]
    if b == 0:
        return a
    mem[a][b] = gcd(b, a % b)
    return mem[a][b]

k = int(input())
ans = 0
mem = [[0 for a in range(k+1)]for b in range(k+1)]
n = k+1
for i in range(1,n):
    for j in range(1,n):
        d = gcd(i,j)
        for k in range(1,n):
            ans += gcd(d,k)
print(ans)
### BUGGY CODE ###

import sys

stdin = sys.stdin

mod = 1000000007
inf = 1 << 60

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n, k = na()
h = na()

dp = [inf] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))

print(dp[n - 1])

### FIXED CODE ###

import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n, k = na()
h = na()

inf = 1 << 60
dp = [inf for i in range(n)]
dp[0] = 0

for i in range(n):
    p = min(i + k + 1, n)
    for j in range(i + 1, p):
        dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))
print(dp[n - 1])
### BUGGY CODE ###

N = int(input())
claim = []
MAX = 0

for i in range(N):
    A = int(input())
    claim.append([input().split() for i in range(A)])

for i in range(2 ** N):
    people = [0 for i in range(N)]
    FLAG = True
    for j in range(N):  
        if ((i >> j) & 1):  
            people[j] = 1

    c = [claim[i] for i in range(N) if people[i] == 1]
    
    for k in range(len(c)):
        for l in range(len(c[k])):
            if people[int(c[k][l][0]) - 1] != int(c[k][l][1]):
                FLAG = False
    
    if FLAG:
        MAX = max(MAX, sum(people))

print(MAX)

### FIXED CODE ###

N = int(input())
claim = []
MAX = 0

for i in range(N):
    A = int(input())
    claim.append([input().split() for i in range(A)])

for i in range(2 ** N):
    people = [0 for i in range(N)]
    FLAG = True
    for j in range(N):  
        if ((i >> j) & 1):  
            people[j] = 1
    
    for k in range(len(claim)):
        if people[k] == 0:
            continue
        for l in range(len(claim[k])):
            if people[int(claim[k][l][0]) - 1] != int(claim[k][l][1]):
                FLAG = False
                break
    
    if FLAG:
        MAX = max(MAX, sum(people))

print(MAX)
### BUGGY CODE ###

import re
import copy

def getDevidedString(S):
    s = copy.deepcopy(S)
    regExDream = "^(.*)dream$"
    if re.match(regExDream, s):
        return s[0:-5]
    regExDreamer = "^(.*)dreamer$"
    if re.match(regExDreamer, s):
        return s[0:-7]
    regExErase = "^(.*)erase$"
    if re.match(regExErase, s):
        return s[0:-5]
    regExEraser = "^(.*)eraser$"
    if re.match(regExEraser, s):
        return s[0:-6]
    return s

S = input()

while len(S) != 0:
    tmp = getDevidedString(S)
    if len(S) != len(tmp):
        S = tmp
    else:
        break

if len(S)== 0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

d = ["dream", "dreamer", "erase", "eraser"]

def getDevidedString(s):
    i = 0
    while i < 4:
        position = len(d[i]) * -1
        str = s[position:]
        if str == d[i]:
           return s[0:position]
        i += 1
    return s

S = input()

while len(S) != 0:
    tmp = getDevidedString(S)
    if len(S) != len(tmp):
        S = tmp
    else:
        break

if len(S)== 0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

N = int(input())
L = [int(i) for i in input().split()]
 
result = 0
 
for aIndex,a in enumerate(L):
    for bIndex,b in enumerate(L[aIndex+1:]):
        for c in L[aIndex+bIndex+2:]:
            if a<b+c and b<a+c and c<a+b:
                result+=1
 
print(result)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int,input().split()))
L.sort()
 
result = 0

for aIndex,a in enumerate(L[:N-2]):
    for bIndex,b in enumerate(L[aIndex+1:N-1]):
        bIndex = aIndex + bIndex + 1
        ab = a+b
        n = bisect_left(L,ab) - bIndex - 1
        result += n
print(result)
### BUGGY CODE ###

import numpy as np
n,m,k=map(int,input().split())
A=[0]+list(map(int, input().split()))
B=[0]+list(map(int, input().split()))
ans=0
a=np.cumsum(np.array(A))
b=np.cumsum(np.array(B))
for i in range(n+1):
    if k>=a[i]:
        j=m
        while b[j]>k-a[i]:
            j-=1
        ans=max(ans,i+j)
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
ans=0
a, b=[0], [0]
for i in range(n):
    a.append(a[i]+A[i])
for i in range(m):
    b.append(b[i]+B[i])
j=m
for i in range(n+1):
    if k<a[i]:
        break
    while b[j]>k-a[i]:
        j-=1
    ans=max(ans,i+j)
print(ans)
### BUGGY CODE ###

D = int(input())
c = list(map(int, input().split()))
S = []
for i in range(D):
    S.append(list(map(int, input().split())))

nocontest = [1 for i in range(26)]

for i in range(D):
    s = S[i]
    contest = [0 for j in range(26)]
    for j in range(26):
        contest[j] = c * nocontest[j] * s[j]
    max_contest = max(contest)
    ans = contest.index(max_contest)
    print(ans + 1)
    
    for i in range(26):
        if i == ans:
            nocontest[i] = 1
        else:
            nocontest[i] += 1
    #print(nocontest)

### FIXED CODE ###

D = int(input())

for i in range(D):
    print(1)
### BUGGY CODE ###

N = input()
B = []

for a in input().split():
  B.append(a)
  B = B[::-1]
print(*B)  

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
s = input().split()
q = deque()

for i in range(n):
  if i%2 == 0:
    q.appendleft(s[i])
  else:
    q.append(s[i])
if n%2 == 0:
  q.reverse()
print(" ".join(q))
### BUGGY CODE ###

from collections import Counter

def factorization(n):
    counter = Counter()
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            counter[i] = cnt

    if temp!=1:
        counter[temp] = 1

    if len(counter)==0:
        counter[n] = 1

    return counter

def main():
    mod = 10**9+7
    N = int(input())
    A = list(map(int,input().split()))
    
    A_primefact = [0]*N
    union = Counter()
    for i in range(N):
        A_primefact[i] = factorization(A[i])
        union = union | A_primefact[i]
    ans = 0
    for i in range(N):
        tmp = 1
        for prime in (union-A_primefact[i]).most_common():
            tmp *= prime[0]**prime[1]
            tmp %= mod
        ans += tmp
        ans %= mod
    ans %= mod
    
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import fractions

def main():
    mod = 10**9+7
    N = int(input())
    A = list(map(int,input().split()))
    lcm = 1
    for Ai in A:
        lcm = lcm*Ai//fractions.gcd(lcm,Ai)
    lcm %= mod
    ans = 0
    for Ai in A:
        ans += lcm*pow(Ai,mod-2,mod)%mod
        ans %= mod
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

Nlist = list(range(int(input())))
lst = []
for i in Nlist:
    lst.append(int(input()))

n=0
for i in Nlist:
    n,lst[i] = lst[i],n
    print(max(lst))
    n,lst[i] = lst[i],n



### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
B = sorted(A, reverse = True)

for i in range(N):
    if A[i] == B[0]:
        print(B[1])
    else:
        print(B[0])
### BUGGY CODE ###

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

dp = [1000000000] * n

dp[0] = 0

for i in range(1, n):

    if i == 1:
        dp[1] = abs(h[1] - h[0])
    else:
        dp[i] = min([dp[i-j] + abs(h[i-j] - h[i]) for j in range(1, k+1)])

print(dp[-1])


### FIXED CODE ###

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

dp = [1000000000] * n

dp[0] = 0

for i in range(1, n):

    if i == 1:
        dp[1] = abs(h[1] - h[0])
    else:
        dp[i] = min([dp[i-j] + abs(h[i-j] - h[i]) for j in range(1, k+1)])

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

n=int(input())
p=[]
for i in input().split():
  p+=[int(i.split(".")[1])]
dp=[[0]*(n+1) for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
  dp[i+1][0]=dp[i][0]*(100-p[i])
  for j in range(i+1):
    dp[i+1][j+1]=dp[i][j]*p[i]+dp[i][j+1]*(100-p[i])
print(sum([dp[n][i] for i in range((n+1)//2,n+1)])/pow(100,n))

### FIXED CODE ###

n=int(input())
p=list(map(float,input().split()))
dp=[[0 for _ in range(n+1)]for _ in range(n)]
dp[0][0]=1-p[0]
dp[0][1]=p[0]
for i in range(1,n):
  for j in range(i+2):
    dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i])
print(sum(dp[-1][(n+1)//2:]))
### BUGGY CODE ###

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

Ans=1

for A in range(N):
    NewAns=Ans*As[A]
    Ans=NewAns
if Ans>10**18:
    Ans=-1

print(Ans)

### FIXED CODE ###

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

Ans=1
if As.count(0):
    print(0)
    exit()
else:
    for A in range(N):
        if Ans>10**18:
            Ans=-1
            print(Ans)
            exit()
        else:
            NewAns=Ans*As[A]
            Ans=NewAns
    if Ans>10**18:
        Ans=-1
    
    print(Ans)
### BUGGY CODE ###

n=int(input())

for i in range(1,n**2+1):
    a=i
    if n%a==0:
        b=n//a
        sa=str(a)
        sb=str(b)
        
        #print(a,b,len(sa),len(sb))
        if len(sb)-len(sa)==0:
            ans=len(sb)
            break
        elif len(sb)-len(sa)>=1:
             ans=len(sb)
        else:
            #print(b,sb,len(sa),len(sb))
            break

print(ans)

### FIXED CODE ###

n=int(input())

for a in range(1,int(n**0.5+1)):
    if n%a==0:
        b=n//a
        sa=str(a)
        sb=str(b)
        if a<=b:
             ans=len(sb)
        else:
            break

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

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

INF=float("inf")

dp=[INF]*N
dp[0]=0

for i in range(0, N-1):
  for k in range(1, K+1):
    if i+k <= N-1:
      dp[i+k]=min(dp[i+k],dp[i]+abs(A[i]-A[i+k]))
print(dp[N-1])


### FIXED CODE ###

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

def solve():
    """ dp[i+k]を求める方法
    TLE 
    """
    N,K=list(map(int,input().split()))
    A=list(map(int,input().split()))
    
    INF=float("inf")
    
    dp=[INF]*N
    dp[0]=0
    
    for i in range(0, N-1):
        for k in range(1, K+1):
            if i+k <= N-1:
                dp[i+k]=min(dp[i+k],dp[i]+abs(A[i]-A[i+k]))
            else:
                break
    print(dp[N-1])


def solve2():
    """dp[i]を求める方法
    """
    N,K=list(map(int,input().split()))
    A=list(map(int,input().split()))
    
    INF=float("inf")
    
    dp=[INF]*N
    dp[0]=0
    for i in range(1, N):
        for k in range(1, K+1):
            if i-k >= 0:
                dp[i] = min(dp[i], dp[i-k]+abs(A[i]-A[i-k]))
            else:
                break
    print(dp[N-1])


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

N, S = map(int,input().split())
A = [int(s) for s in input().split()]
DP = [[0 for j in range(S + 1)] for i in range(N + 1)]
mod = 998244353
DP[0][0] = 1

for i in range(N):
  for j in range(S + 1):
    DP[i + 1][j] += 2 * DP[i][j]
    DP[i + 1][j] %= mod
    if j + A[i] <= S:
      DP[i + 1][j + A[i]] += DP[i][j]
    DP[i + 1][j] %= mod

print(DP[N][S])

### FIXED CODE ###

N, S = map(int,input().split())
A = [int(s) for s in input().split()]
DP = [[0 for j in range(S + 1)] for i in range(N + 1)]
mod = 998244353
DP[0][0] = 1

for i in range(N):
  for j in range(S + 1):
    DP[i + 1][j] += 2 * DP[i][j]
    DP[i + 1][j] %= mod
    if j + A[i] <= S:
      DP[i + 1][j + A[i]] += DP[i][j]
      DP[i + 1][j + A[i]] %= mod

print(DP[N][S])
### BUGGY CODE ###


D, G = map(int, input().split())
pc = [tuple(map(int, input().split())) for _ in range(D)]

memo = dict()


def rec(crp, crscore, crans):
    global D, G, pc, memo

    if (crp, crscore, crans) in memo:
        return memo[(crp, crscore, crans)]

    if crscore >= G:
        return crans
    elif crp > D:
        return 10**9

    p, c = pc[crp - 1]

    tmp_min = min(
        rec(crp + 1, crscore + 100 * crp * i, crans + i) for i in range(p)
    )

    res = min(tmp_min, rec(crp + 1, crscore + 100 * crp * p + c, crans + p))
    memo[(crp, crscore, crans)] = res
    return res


print(rec(1, 0, 0))


### FIXED CODE ###

from itertools import product


D, G = map(int, input().split())
pc = [tuple(map(int, input().split())) for _ in range(D)]


ans = 1e9
for selected in product((True, False), repeat=D):
    tmp_score = 0
    tmp_count = 0
    rest_max = 0

    for i, is_select in enumerate(selected):
        if is_select:
            tmp_score += 100 * (i + 1) * pc[i][0] + pc[i][1]
            tmp_count += pc[i][0]
        else:
            rest_max = i

    if tmp_score < G:
        s1 = 100 * (rest_max + 1)
        need = (G - tmp_score + s1 - 1) // s1

        if need >= pc[rest_max][0]:
            continue

        tmp_count += need

    ans = min(ans, tmp_count)

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

import re
n,q = map(int, input().split())
str = input()
for i in range(q):
  l,r = map(int, input().split())
  sub_str = str[(l-1):r]
  print(len(re.findall('AC', sub_str)))


### 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])