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

N, W = map(int, input().split())
dp = [-1] * (W+1)
dp[0] = 0

for i in range(N):
    w, v = map(int, input().split())
    for j in range(W-w, -1, -1):
        if dp[j] >= 0:
            dp[j+w] = max(dp[j+w], dp[j] + v)

ans = max(dp)
print(ans)


### FIXED CODE ###

N, W = map(int, input().split())
dp = [-1] * (W+1)
dp[0] = 0

for i in range(N):
    w, v = map(int, input().split())
    for j in range(W-w, -1, -1):
        if dp[j] == -1:
            continue
        else:
            dp[j+w] = max(dp[j+w], dp[j] + v)

print(max(dp))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1

""" Input
N = int(input())
N, A, B = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(input().split(), dtype=np.float64)
D = [int(input()) for _ in range(N)]
AB = [[int(x) for x in input().split()] for _ in range(N)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
"""

S = input().rstrip()

counter = 0
for l_index in range(len(S) - 4):
    atama = int(S[l_index:l_index+2])
    if atama % 2 != 0:
        continue
    else:
        r_index = 5
        while True:
            saigo = l_index + r_index
            if saigo > len(S):
                break
            kouho = int(S[l_index:saigo])
            if kouho % 2019 == 0:
                counter += 1
                r_index += 5
                continue
            r_index += 1


print(counter)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1
MOD = 2019

"""
gcd(10, 2019) = 1 互いに素
-> 10のmod2019での逆元(1/10)が存在
"""
S = input().rstrip()
s_list = list(map(int, list(S)))[::-1]

counts = [0] * MOD
counts[0] = 1

num, d = 0, 1

for s_element in s_list:
    num += s_element * d
    num %= MOD
    d *= 10
    d %= MOD
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

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

N=int(input())
S=input()



ans=0
for i2 in range(10):
  for j in range(10):
    for k in range(10):
      s='{}{}{}'.format(i2,j,k)
      isOne=0
      isTen=0
      isHundred=0
      for i in range(N) :
        if S[i]==s[0] and isOne==0:
          isOne=1
        elif S[i]==s[1] and isOne==1 and isTen==0:
          isTen=1
        elif S[i]==s[2] and isOne==1 and isTen==1 and isHundred==0:
          isHundred=1
      if isHundred==1:
        ans+=1

print(ans)

### FIXED CODE ###

N=int(input())
S=input()
S=list(map(int,S))
ans=0
for s in range(1000):
      A=s//100
      B=(s-A*100)//10
      C=s-A*100-B*10
      isOne=0
      isTen=0
      isHundred=0
      for i in range(N) :
        if isOne==0:
          if S[i]==A: 
            isOne=1
        elif isTen==0:
          if S[i]==B: 
            isTen=1
        elif isHundred==0:
          if S[i]==C:
            isHundred=1
            ans+=1
        else:
          break

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

import numpy as np

N, K, Q = [int(value) for value in input().split(' ')]
A = []

for _ in range(Q):
    A.append(int(input()))

points = np.full(N, K)

for i in range(Q):
    points = points - 1
    points[A[i] - 1] += 1

for point in points:
    if point > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K, Q = [int(value) for value in input().split(' ')]
A = [int(input()) for _ in range(Q)]

points = [K - Q] * N

for value in A:
    points[value - 1] += 1

for point in points:
    if point <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import math

N = int(input())

output = 0

for i in range(1, N):
    counter = 0
    for j in range(1, int(math.sqrt(i)+1)):
        if i % j == 0:
            counter += 1
    if int(math.sqrt(i)) == math.sqrt(i):
        counter -= 1
        counter *= 2
        counter += 1
    else :
        counter *= 2
    output += counter
    
print(output)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1, n):
  ans += (n - 1) // a
print(ans)
### BUGGY CODE ###

m = 1000000
NIL = -1

def h1(key):
    return key % m

def h2(key):
    return 1 + (key % (m - 1))

def h(key, i):
    return (h1(key) + i * h2(key)) % m

def insert(t, key):
    i = 0
    while True:
        j = h(key, i)
        if t[j] == NIL:
            t[j] = key
            return j
        else:
            i += 1

def find(t, key):
    i = 0
    while True:
        j = h(key, i)
        if t[j] == key:
            return j
        elif t[j] == NIL or i >= m:
            return NIL
        else:
            i += 1

def convert(word):
    result = ""
    for i in word:
        if i == "A":
            result += "1"
        elif i == "T":
            result += "2"
        elif i == "G":
            result += "3"
        else:
            result += "4"
    return int(result)


t = [NIL]*m
n = int(input())
for i in range(n):
    com = input().split()
    key = convert(com[1])
    if com[0] == "insert":
        insert(t, key)
    else:
        if find(t, key) != NIL:
            print("yes")
        else:
            print("no")



### FIXED CODE ###

n = int(input())
d = set()

for i in range(n):
    com = input().split()
    if com[0] == "insert":
        d.add(com[1])
    else:
        print("yes" if com[1] in d else "no")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
dic = {}
for i in range(len(a)):
    dic.setdefault(a[i], a.count(a[i]))
ans = 0
for i in dic.values():
    if i > 1:
        ans += i*(i-1)//2
for i in a:
    print(ans - (dic[i] - 1))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = 0
ans = 0
dic = {}
for i in a:
    if i not in dic.keys():
        dic[i] = 1
    else:
        dic[i] += 1
for i in dic.values():
    ans += i*(i-1)//2
for i in a:
    print(ans - (dic[i] - 1))
### BUGGY CODE ###

N, M = map(int, input().split())
A = {}
ac = []
total=0
count = 0
for i in range(M):
    p, s = map(str, input().split())
    if int(p) not in ac:
        if int(p) not in A.keys(): 
            if int(p) >0 and int(p) <=N :
                if s == "WA":
                    A[int(p)] =1
                elif s =="AC":
                    A[int(p)] =0
                    ac.append(int(p))
                    count += 1
        elif int(p) in A.keys():
            if s == "WA":
                    A[int(p)] +=1
            elif s =="AC":
                    A[int(p)] +=0
                    ac.append(int(p))
                    count += 1
                    total += A[int(p)]

print(count,total)

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
AC = np.array([0]*N)
WA = np.array([0]*N)

for i in range(M):
    p, s = map(str, input().split())
    if AC[int(p)-1] == 0 and s =="WA":
        WA[int(p)-1] += 1
    else:
        AC[int(p)-1] = 1
        

print(sum(AC), sum(AC*WA))
### BUGGY CODE ###

N, M = map(int, input().split())
dic = {i: [] for i in range(1, N + 1)} 
X_list = []
Y_list = []
for i in range(M):
  X, Y = map(int, input().split())
  dic[X].append(Y)
  X_list.append(X)
  Y_list.append(Y)
for j in range(1, N + 1):
  dic[j].sort()
for x, y in zip(X_list, Y_list):
  print(str(x).zfill(6)+str(dic[x].index(y) + 1).zfill(6))

### FIXED CODE ###

N, M = map(int, input().split())
XY_list = [[] for i in range(N)]
ans_list = [None] * M
for i in range(M):
  X, Y = map(int, input().split())
  XY_list[X - 1].append((Y, i))
for j, k in enumerate(XY_list):
  k.sort()
  for l, (y, m) in enumerate(k):
    ans_list[m] = str(j + 1).zfill(6) + str(l + 1).zfill(6)
print(*ans_list, sep = "\n")
### BUGGY CODE ###

from collections import Counter
s = input()
# 累積和の準備
sum_list = [0]*(len(s)+1)  # s[0]は０であってほしいから配列数ひとつおおい
for i in range(1, len(s) + 1):
    sum_list[i] += (sum_list[i-1] + int(s[len(s)-i])*10**(i-1)) % 2019
"""
(s[j]-s[i]/10**i)が区間の整数
区間の整数が2019で割り切れればよい
つまり、(s[j]-s[i]/10**i)≡0 (mod=2019)
ここで10**iと2019(素数)は互いに素なので、
10**iをかけて上の式はs[j]-s[i]≡0 (mod=2019)と同値
s[j]≡s[i] (mod=2019)となる。
"""
# s[i]のmod=2019を記憶しておくリスト用意
#mod_s = [[] for _ in range(len(sum_list))]
#mod_s[0] = 0
#for i in range(1, len(sum_list)):
    #mod_s[i] = sum_list[i] % 2019

#print(mod_s)
#c = Counter(mod_s)
c = Counter(sum_list)
ans = 0
#print(c)
for value in c.values():
    ans += value*(value-1)//2
print(ans)






### FIXED CODE ###

from collections import Counter
s = input()
n = len(s)
# 累積和の準備
sum_list = [0]*(n+1)  # s[0]は０であってほしいから配列数ひとつおおい
_10 = 1
for i in range(1, n + 1):
    sum_list[i] += (sum_list[i-1] + int(s[n-i])*_10 % 2019) % 2019  # ここでmodしておく
    _10 = _10*10 %2019
"""
(s[j]-s[i]/10**i)が区間の整数
区間の整数が2019で割り切れればよい
つまり、(s[j]-s[i]/10**i)≡0 (mod=2019)
ここで10**iと2019(素数)は互いに素なので、
10**iをかけて上の式はs[j]-s[i]≡0 (mod=2019)と同値
s[j]≡s[i] (mod=2019)となる。
"""
c = Counter(sum_list)
ans = 0

for key in c.keys():
    ans += c[key]*(c[key]-1)//2
print(ans)
### BUGGY CODE ###

from collections import deque
import copy
INF = 20 * 20 + 1

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]

    ans = 0
    goal_dists_base = [[-1 for _ in range(W+2)] for _ in range(H)]
    goal_dists_base = [[-1 for _ in range(W+2)]] + goal_dists_base + [[-1 for _ in range(W+2)]]
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '#':
                goal_dists_base[h+1][w+1] = -1
            else:
                goal_dists_base[h+1][w+1] = INF

    for hs in range(H):
        for ws in range(W):
            if maze[hs][ws] == '#':
                continue
            
            goal_dists = copy.deepcopy(goal_dists_base)
            goal_dists[hs+1][ws+1] = 0
            d = deque([[hs+1, ws+1]])
            while len(d) > 0:
                ht, wt = d.popleft()
                dist = goal_dists[ht][wt]
                for dh, dw in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    if goal_dists[ht+dh][wt+dw] > dist:
                        goal_dists[ht+dh][wt+dw] = dist + 1
                        d.append([ht+dh, wt+dw])
            
            max_dist = 0
            for h in range(1, H+2):
                for w in range(1, W+2):
                    if goal_dists[h][w] == INF:
                        continue
                    max_dist = max(max_dist, goal_dists[h][w])
            ans = max(ans, max_dist)

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
import copy
INF = 20 * 20 + 1

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]

    ans = 0
    goal_base = [[-1 for _ in range(W+2)] for _ in range(H)]
    goal_base = [[-1 for _ in range(W+2)]] + goal_base + [[-1 for _ in range(W+2)]]
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '#':
                goal_base[h+1][w+1] = -1
            else:
                goal_base[h+1][w+1] = INF

    for hs in range(H):
        for ws in range(W):
            if maze[hs][ws] == '#':
                continue

            goal_dists = copy.deepcopy(goal_base)
            goal_dists[hs+1][ws+1] = 0
            d = deque([[hs+1, ws+1]])
            while len(d) > 0:
                ht, wt = d.popleft()
                dist = goal_dists[ht][wt]
                for dh, dw in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    if goal_dists[ht+dh][wt+dw] == INF:
                        goal_dists[ht+dh][wt+dw] = dist + 1
                        d.append([ht+dh, wt+dw])
            
            max_dist = [goal_dists[h][w] for w in range(1, W+2) for h in range(1, H+2) if goal_dists[h][w] != INF]
            ans = max(ans, max(max_dist))

    print(ans)

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

import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from operator import mul

n = int(input())
l = list(map(int, input().split()))
ans = reduce(mul, l)

if ans > 10**18:
    print (-1)
else:
    print(ans)

### FIXED CODE ###

import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from sys import stdin
input = stdin.readline



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

ans = 1
ng = False
for i in range(n):
    if l[i] == 0:
        print(0)
        quit()
    if not ng:
        ans *= l[i]
        if ans > 10**18:
            ng = True

if ng:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

#import numpy as np
n=int(input())
strl=[list(input()) for i in range(n)]

count=0
#il=np.arange(n)
for i in range(n) :
  sal=strl[i]
  jl=list(range(i+1,n))
  for j in jl :
    flag=True
    sbl=strl[j]
    sal.sort()
    sbl.sort()
    if sal==sbl:
      count+=1
print(count)

### FIXED CODE ###

#import numpy as np
n=int(input())
strl=[list(input()) for i in range(n)]

count=0
pt={}
#il=np.arange(n)
for i in range(n) :
  sal=strl[i]
  sal.sort()
  temp="".join(sal)
  if temp in pt.keys() :
    #ptがある
    tempc=pt[temp]
    count+=tempc
    pt[temp]=tempc+1
  else :
    pt[temp]=1
print(count)
#print(count)
### BUGGY CODE ###

S = input()
Q = int(input())

cnt = 0
for i in range(Q):
    query = input().split()
    if(query[0] == "1"):
        cnt += 1
    else:
        if(query[1] == "1"):
            if(cnt%2 == 0):
                S = query[2]+S
            else:
                S = S[::-1]
                S = query[2]+S
            cnt = 0
        else:
            if(cnt%2 == 0):
                S = S+query[2]
            else:
                S = S[::-1]
                S = S+query[2]
            cnt = 0
if(cnt%2 == 0):
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

from collections import deque

def main():
    S = input()
    Q = int(input())
    
    SS = deque()
    for s in S:
        SS.append(s)
    
    cnt = 0
    for i in range(Q):
        query = input().split()
        if(query[0] == "1"):
            cnt += 1
        else:
            if(query[1] == "1"):
                if(cnt%2 == 0):
                    SS.appendleft(query[2])
                else:
                    SS.append(query[2])
            else:
                if(cnt%2 == 0):
                    SS.append(query[2])
                else:
                    SS.appendleft(query[2])
    
    ans = list(SS)
    if(cnt%2 == 0):
        print(''.join(ans))
    else:
        print(''.join(ans[::-1]))
main()
### BUGGY CODE ###

from collections import deque
def hate(x,y):
    cur_hate = 0
    cur_q = deque()
    next_q = deque()
    cur_q.append((x,y))
    already = set()
    while True:
        while cur_q:
            x,y = cur_q.popleft()
            for i in range(4):
                next_x = x+dx[i]
                next_y = y+dy[i]
                if not (next_x,next_y) in already:
                    if grid[next_y][next_x] == "o":
                        return cur_hate
                    if grid[next_y][next_x] == "#":
                        next_q.append((next_x,next_y))
                    else:
                        cur_q.append((next_x,next_y))
                    already.add((x,y))
        cur_hate += 1
        cur_q = next_q
        next_q = deque()
n = int(input())
grid = []
grid.append(["o"]*(n+2))
for i in range(n):
    grid.append(["o"]+["#"]*n+["o"])
grid.append(["o"]*(n+2))
dx = [0,1,0,-1]
dy = [1,0,-1,0]
ans = 0
p = list(map(int,input().split()))
for i in range(n**2):
    pos = p[i]
    x = (pos-1)%n+1
    y = (pos-1)//n+1
    ans += hate(x,y)
    if hate(x,y) == 0:
        grid[y][x] = "o"
    else:
        grid[y][x] = "."
print(ans)

### FIXED CODE ###

import sys
import numpy as np
from numba import njit

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

@njit('(i4,i4[:])',cache=True)
def main(n,p):
    ans = 0
    w = n+2
    grid = np.ones((w,w),np.int32)
    dis = np.zeros((w,w),np.int32)
    for i in range(1,n+1):
        for j in range(1,n+1):
            dis[i][j] = min(i,n-i+1,j,n-j+1)-1
    grid = grid.ravel()
    dis = dis.ravel()
    stack = np.empty_like(grid)
    for pos in p:
        pos -= 1
        x = pos % n + 1
        y = pos // n + 1
        v = y*w+x
        ans += dis[v]
        grid[v] = 0
        k = min(dis[v-1],dis[v+1],dis[v+w],dis[v-w])
        cur = 0
        stack[0] = v
        while cur >= 0:
            v = stack[cur]
            cur -= 1
            for dx in (-1,1,w,-w):
                next_v = v + dx
                k = dis[v]+grid[v]
                if dis[next_v] > k:
                    dis[next_v] = k
                    cur += 1
                    stack[cur] = next_v
    return ans

n = int(readline())
p = np.array(readline().split(),np.int32)
print(main(n,p))
### BUGGY CODE ###

from itertools import groupby
from heapq import heapify, heappop

N, K = map(int, input().split())
sushi = [tuple(map(int, input().split())) for _ in range(N)]

sushi.sort(key=lambda x: (x[1], x[0]), reverse=True)

maxs = []
rems = []
kinds = set()
for k, g in groupby(sorted(sushi[:K], key=lambda x: x[0]), key=lambda x: x[0]):
    d = list(list(zip(*g))[1])
    maxs.append(d.pop(0))
    rems.extend(d)
    kinds.add(k)
heapify(rems)
ans = sum(maxs) + sum(rems) + len(kinds)**2

for t, d in sushi[K:]:
    if not rems:
        break
    if t in kinds:
        continue
    maxs.append(d)
    heappop(rems)
    kinds.add(t)
    ans = max(ans, sum(maxs) + sum(rems) + len(kinds)**2)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]
sushi.sort(key=lambda x: x[1], reverse=True)

score = 0

remains = []
kinds = set()
for t, d in sushi[:K]:
    if t in kinds:
        remains.append(d)
    kinds.add(t)
    score += d
score += len(kinds)**2

test = score
for t, d in sushi[K:]:
    if not remains:
        break
    if t in kinds:
        continue
    kinds.add(t)
    rm = remains.pop()
    test = test + (d - rm) + (len(kinds)*2 - 1)
    score = max(score, test)

print(score)
### BUGGY CODE ###

H,W,N = map(int,input().split())
B=[[0 for k in range(W-2)] for j in range(H-2)]
li=[-1,0,1]
Nli=[]
for k in range(N):
    a,b=map(int,input().split())
    for n in range(3):
        for m in range(3):
            if 0<=a-2-li[m]<H-2 and 0<=b-2-li[n]<W-2:
                Nli.append((b-2-li[n])*(H-2)+(a-2-li[m]))
import collections
s = collections.Counter(Nli)
v = list(s.values())
print((H-2)*(W-2)-len(set(Nli)))
for k in range(1,10):
    print(v.count(k))

### FIXED CODE ###

H,W,N = map(int,input().split())
Nli=[]
for k in range(N):
    a,b=map(int,input().split())
    for n in range(-1,2):
        for m in range(-1,2):
            if 0<=a-2-m<H-2 and 0<=b-2-n<W-2:
                Nli.append((b-n)*(H)+(a-m))
import collections
s = collections.Counter(Nli)
v = list(s.values())
print((H-2)*(W-2)-len(set(Nli)))
for k in range(1,10):
    print(v.count(k))
### BUGGY CODE ###

INF = 10**9
N, K = map(int, input().split())
h = list(map(int, input().split()))
cost = [INF] * N
cost[0] = 0
for i in range(1, N):
  for j in range(1, min(i, K)+1):
    cost[i] = min(cost[i], cost[i-j] + abs(h[i] - h[i-j]))
print(cost[N-1])

### FIXED CODE ###

INF = 10**9
N, K = map(int, input().split())
h = list(map(int, input().split()))
cost = [INF] * N
cost[0] = 0
for i in range(1, N):
  for j in range(1, min(i, K)+1):
    cost[i] = min(cost[i], cost[i-j] + abs(h[i] - h[i-j]))
print(cost[N-1])
### BUGGY CODE ###

def main():
    from itertools import accumulate
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        for i,t in enumerate(a):
            b[i-t if i>t else 0]+=1
            if i-~t<n:b[i-~t]-=1
        *a,=accumulate(b)
        if min(a)==n:break
    print(' '.join(map(str,a)))
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()
### BUGGY CODE ###

# tokio marine 2020 C.Lamps
import copy
# N = int(input())
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

for i in range(K):
    B = [0 for k in range(N)]
    for j in range(N):
        L = A[j]
        l = max(j-L, 0)
        r = min(j+L, N-1)
        B[l] += 1
        if r + 1 < N:
            B[r+1] -= 1
    for j in range(1, N):
        B[j] += B[j-1]
    A = copy.deepcopy(list(B))
    if len(set(A)) == 1 and A[0] == N:
        break
print(*A)


### FIXED CODE ###

# tokio marine 2020 C.Lamps
import copy
# N = int(input())
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

for i in range(K):
    B = [0 for k in range(N)]
    for j in range(N):
        L = A[j]
        l = max(j-L, 0)
        r = min(j+L, N-1)
        B[l] += 1
        if r + 1 < N:
            B[r+1] -= 1
    for j in range(1, N):
        B[j] += B[j-1]
    A = copy.deepcopy(list(B))
    if len(set(A)) == 1 and A[0] == N:
        break
print(*A)
### BUGGY CODE ###

mod = 998244353
a,b,c,d = map(int,input().split())
dp = [[0 for _ in range(d+1)] for _ in range(c+1)]

dp[a][b] = 1
if d > b:
    dp[a][b+1] = a
if c > a:
    dp[a+1][b] = b
for i in range(b+2,d+1):
    dp[a][i] = dp[a][i-1]*a%mod

for i in range(a+2,c+1):
    dp[i][b] = dp[i-1][b]*b%mod

for i in range(a+1,c+1):
    for j in range(b+1,d+1):
        dp[i][j] = dp[i][j-1] * i % mod + dp[i-1][j] * j % mod - dp[i-1][j-1]*(i-1)*(j-1)%mod

#print(dp)
print(dp[c][d] % mod)

### FIXED CODE ###

mod = 998244353
a,b,c,d = map(int,input().split())
dp = [[0 for _ in range(d+1)] for _ in range(c+1)]

dp[a][b] = 1
if d > b:
    dp[a][b+1] = a
if c > a:
    dp[a+1][b] = b
for i in range(b+2,d+1):
    dp[a][i] = dp[a][i-1]*a%mod

for i in range(a+2,c+1):
    dp[i][b] = dp[i-1][b]*b%mod

for i in range(a+1,c+1):
    for j in range(b+1,d+1):
        dp[i][j] = (dp[i][j-1] * i % mod + dp[i-1][j] * j % mod - dp[i-1][j-1]*(i-1)*(j-1)%mod + mod) % mod

#print(dp)
print(dp[c][d] % mod)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
h.sort(reverse=True)
for i in range(k):
  try:
    h.pop(0)
  except IndexError:
    pass
print(sum(h))

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
h.sort()
for i in range(k):
  try:
    h.pop(-1)
  except IndexError:
    pass
print(sum(h))
### BUGGY CODE ###

import math
S_list = list(input())
n = len(S_list)
x = 0
Timod_list = []

for i in range(n):
  Ti_list = S_list[i:n+1]
  Ti_str = ""
  for y in Ti_list:
    Ti_str = Ti_str + y
  Ti = int(Ti_str)
  Timod = Ti % 2019
  Timod_list = Timod_list + [Timod]

Timod_list.sort()
Timodlist_len= len(Timod_list)

Tlist0 = Timod_list.count(0)
x = x + Tlist0

for j in range(Timodlist_len-1):
  if Timod_list[j] == Timod_list[j + 1]:
    Tlist = Timod_list.count(Timod_list[j])
    x = x + 1 / 2 * math.factorial(Tlist) / (Tlist - 1)
    
x = int(x)
print(x) 

### FIXED CODE ###

S = input()
Sliststr = list(S)
Slist = [int(s) for s in Sliststr]
Smod = [0]
mod10 = [1]
count = [0]*2019
ans = 0
for i in range(len(S)-1):
  mod10.append(mod10[i]*10%2019)
for i in range(len(S)):
  Smod.append((Smod[i]+Slist[-i-1]*mod10[i])%2019)
for i in range(len(Smod)):
  count[Smod[i]] += 1
for i in range(2019):
  ans += count[i] * (count[i]-1) // 2
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

tmp = []
ans = 0
for i in range(n):
    tmp.append(pl[i]*(pl[i]+1)/2/pl[i])
    if i >= k-1:
        if sum(tmp[i-k+1:i+1]) > ans:
            ans = sum(tmp[i-k+1:i+1])
print(ans)

### FIXED CODE ###

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

dp = [0] * (n + 1)

for i in range(n):
    dp[i+1] = dp[i] + (pl[i] + 1)/2

ans = 0
for i in range(k, n+1):
    ans = max(ans, dp[i] - dp[i-k])

print(ans)