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

N,T = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]

from collections import defaultdict
dp0 = defaultdict(lambda: 0)
dp1 = defaultdict(lambda: 0)
dp0[0] = 0
dp1[0] = 0

for i,(a,b) in enumerate(AB):
    _dp0 = defaultdict(lambda: 0)
    _dp1 = defaultdict(lambda: 0)
    for k0,v0 in dp0.items():
        _dp0[k0] = max(_dp0[k0], v0)
        if k0+a < T:
            _dp0[k0+a] = max(_dp0[k0+a], v0+b)
        _dp1[k0] = max(_dp1[k0], v0+b)
    for k1,v1 in dp1.items():
        _dp1[k1] = max(_dp1[k1], v1)
        if k1+a < T:
            _dp1[k1+a] = max(_dp1[k1+a], v1+b)
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))

### FIXED CODE ###

N,T = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))
### BUGGY CODE ###

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

grid = [input() for i in range(h)]

L = [[0 for i in range(w)] for j in range(h)]
R = [[0 for i in range(w)] for j in range(h)]
D = [[0 for i in range(w)] for j in range(h)]
U = [[0 for i in range(w)] for j in range(h)]

#左上から
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            L[i][j] = 0
            U[i][j] = 0
        else:
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
            
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

#右下から
for i in reversed(range(h)):
    for j in reversed(range(w)):
        if grid[i][j] == "#":
            R[i][j] = 0
            D[i][j] = 0
        else:
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1
                
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1


ans = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            continue
        tmp = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

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

grid = [input() for i in range(h)]

L = [[0 for i in range(w)] for j in range(h)]
R = [[0 for i in range(w)] for j in range(h)]
D = [[0 for i in range(w)] for j in range(h)]
U = [[0 for i in range(w)] for j in range(h)]

#左上から
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            L[i][j] = 0
            U[i][j] = 0
        else:
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
            
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

#右下から
for i in reversed(range(h)):
    for j in reversed(range(w)):
        if grid[i][j] == "#":
            R[i][j] = 0
            D[i][j] = 0
        else:
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1
                
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1


ans = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            continue
        tmp = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, tmp)

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

import sys
import collections

N = int(input())
S = [ch for ch in input()]
counter = collections.Counter(S)
if len(counter.keys()) != 3:
    print(0)
    sys.exit()
total = 1
for k, v in counter.items():
    total *= v

for i in range(len(S)):
    l, r = i - 1, i + 1
    while 0 <= l and r < len(S):
        if len(set([S[i], S[l], S[r]])) == 3:
            total -= 1
        l -= 1
        r += 1
print(total)

### FIXED CODE ###

import sys
import collections

N = int(input())
S = [ch for ch in input()]
counter = collections.Counter(S)
if len(counter.keys()) != 3:
    print(0)
    sys.exit()
total = 1
for k, v in counter.items():
    total *= v

for i in range(len(S)):
    l, r = i - 1, i + 1
    while 0 <= l and r < len(S):
        if len(set([S[i], S[l], S[r]])) == 3:
            total -= 1
        l -= 1
        r += 1
print(total)
### BUGGY CODE ###

MOD=10**9+7

N,M=map(int,input().split())
slist=list(map(int,input().split()))
tlist=list(map(int,input().split()))

dp=[]
for i in range(N+1):
  dp.append([0]*(M+1))
dp[0][0]=1
#print(dp)

answer=1
for i in range(1,N+1):
  for j in range(1,M+1):
    if slist[i-1]==tlist[j-1]:
      for ii in range(i):
        for jj in range(j):
          dp[i][j]+=dp[ii][jj]
          answer+=dp[ii][jj]
          answer%=MOD

#print(dp)
print(answer)

### FIXED CODE ###

MOD=10**9+7

N,M=map(int,input().split())
slist=list(map(int,input().split()))
tlist=list(map(int,input().split()))

dp,dp_sum=[],[]
for i in range(N+1):
  dp.append([0]*(M+1))
  dp_sum.append([1]*(M+1))
dp[0][0]=1
#print(dp)

for i in range(1,N+1):
  for j in range(1,M+1):
    if slist[i-1]==tlist[j-1]:
      dp[i][j]=dp_sum[i-1][j-1]      
    dp_sum[i][j]=(dp[i][j]+dp_sum[i-1][j]+dp_sum[i][j-1]-dp_sum[i-1][j-1])%MOD
#print(dp)
#print(dp_sum)

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

import sys
sys.setrecursionlimit(20000000)
N, Q = [int(i) for i in input().split()]
tree = {i:[] for i in range(1,N+1)}
cost_ls = {i:0 for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

def plus(node, _from):
    #cost_ls[node] += num
    for child in tree[node]:
        if child == _from:
            continue
        cost_ls[child] += cost_ls[node]
        plus(child, node)

for _ in range(Q):
    p, x = map(int, input().split())
    cost_ls[p] += x

plus(1, 0)

print(' '.join(str(cost_ls[i]) for i in range(1,N+1)))

### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

N, Q = map(int, input().split())
V = {i: [] for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

C = {i: 0 for i in range(1, N + 1)}

for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)


propagate(1, 0)

print(' '.join(str(C[i]) for i in range(1, N + 1)))
### BUGGY CODE ###

X=int(input())

for a in range(10**5):
  for b in range(10**5):
    if a**5-b**5==X:print(a,b);exit()
    elif a**5+b**5==X:print(a,-b);exit()

### FIXED CODE ###

X=int(input())

for a in range(10**4):
  for b in range(10**4):
    if a**5-b**5==X:print(a,b);exit()
    elif a**5+b**5==X:print(a,-b);exit()
### BUGGY CODE ###

import sys
import copy

h, w = map(int, input().split())
S = [input() for _ in range(h)]


def get_shortest_steps(S, visited, i, j, l, m, steps):
    if i == l and j == m:
        return steps
    if i == -1 or i == h or j == -1 or j == w:
        return sys.maxsize
    if visited[i][j]:
        return sys.maxsize
    if S[i][j] == "#":
        return sys.maxsize
    visited[i][j] = True
    returned_steps1 = get_shortest_steps(S, copy.deepcopy(visited), i + 1, j, l, m, steps + 1)
    returned_steps2 = get_shortest_steps(S, copy.deepcopy(visited), i, j + 1, l, m, steps + 1)
    returned_steps3 = get_shortest_steps(S, copy.deepcopy(visited), i - 1, j, l, m, steps + 1)
    returned_steps4 = get_shortest_steps(S, copy.deepcopy(visited), i, j - 1, l, m, steps + 1)
    # print(returned_steps1, returned_steps2, returned_steps3, returned_steps4)
    return min(returned_steps1, returned_steps2, returned_steps3, returned_steps4)


result = -1
for i in range(h):
    for j in range(w):
        for l in range(h):
            for m in range(w):
                visited = [[False] * w for _ in range(h)]
                shortest_steps = get_shortest_steps(S, visited, i, j, l, m, 0)
                if shortest_steps == sys.maxsize:
                    continue
                if shortest_steps > result:
                    result = shortest_steps
print(result)


### FIXED CODE ###

import sys
import numpy as np
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        distance = [[-1] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        distance[i][j] = step
        visited[i][j] = True
        while plan:
            y, x, step = plan.pop()
#            print(" ", x, y, step)
            # if step > largest_step:
            #     largest_step = step
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "#" or visited[next_y][next_x]:
                    continue
                distance[next_y][next_x] = distance[y][x] + 1
                visited[next_y][next_x] = True
                plan.appendleft((next_y, next_x, step + 1))
#        print(largest_step)
        # if largest_step > max_step:
        #     max_step = largest_step
        max_step = max(max_step, np.max(np.array(distance)))

print(max_step)
### BUGGY CODE ###

n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        k = 2*j - i
        if k <= n - 1:
            k = 2*j-i
            if s[i] != s[j] and s[j] != s[k] and s[i] != s[k]:
                cnt += 1
print(R*G*B - cnt)

### FIXED CODE ###

n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if j - i <= n - 1 - j:
            if s[i] != s[j] and s[j] != s[2*j - i] and s[i] != s[2*j - i]:
                cnt += 1
print(R*G*B - cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
sum = 1
for i in range(n):
    sum *= a[i]
    if(sum > 10 ** 18 and 0 not in  a):
        print(-1)
        break
else:
    print(sum)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
sum = 1
if 0 in a:
    print(0)
else:
    for i in range(n):
        sum *= a[i]
        if(sum > 10 ** 18):
            print(-1)
            break
    else:
        print(sum)
### BUGGY CODE ###

from math import ceil, log2


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.aggfunc = aggfunc
        self.depth = ceil(log2(length))
        self.data = [init_value] * (2 ** (1 + self.depth) - 1)
        self.origin = 2 ** self.depth - 1

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break


n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

xs = set()
events = []

for s, t, x in stx:
    events.append((s - x, 1, x))
    events.append((t - x, -1, x))
    xs.add(x)
events.sort()

xs = list(xs)
xs.sort()


zaatsu = dict(zip(xs, range(len(xs))))

ub = 10 ** 9 + 1
koujichu = SegmentTree(len(zaatsu), ub, min)

i = 0
for di in d:
    while i < len(events) and events[i][0] <= di:
        if events[i][1] == 1:
            koujichu.update(zaatsu[events[i][2]], events[i][2])
        else:
            koujichu.update(zaatsu[events[i][2]], ub)
        i += 1
    if koujichu.data[0] != ub:
        print(koujichu.data[0])
    else:
        print(-1)


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.readline
n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

stx.sort(key=lambda x: x[2])

ans = [-1] * q
jump = [-1] * q
for s, t, x in stx:
    d_start = bisect_left(d, s - x)
    d_stop = bisect_left(d, t - x, lo=d_start)
    while d_start < d_stop:
        if jump[d_start] == -1:
            ans[d_start] = x
            jump[d_start] = d_stop
            d_start += 1
        else:
            d_start = jump[d_start]

for an in ans:
    print(an)
### BUGGY CODE ###

from functools import reduce
from operator import mul

MOD = 1000000007


def combination(n, r):
  r = min(n - r, r)
  if r == 0:
    return 1
  over = reduce(mul, range(n, n - r, -1))
  under = reduce(mul, range(1, r + 1))

  return over // under


def main():
  N, M, K = [int(i) for i in input().strip().split(' ')]
  c = combination(N * M - 2, K - 2) % MOD

  total = 0
  MAX = max(M, N)
  for xy1 in range(MAX - 1):
    for x2 in range(xy1 + 1, M):
      # diff * n_x1 * n_x2 * combination
      total = (total + (x2 - xy1) * N * N * c) % MOD

    for y2 in range(xy1 + 1, N):
      total = (total + (y2 - xy1) * M * M * c) % MOD

  print(total)


main()

### FIXED CODE ###

def mfactorial(n: int, mod: int) -> int:
  cache = mfactorial.__cache if hasattr(mfactorial, '__cache') else [1, 1]
  n_len = len(cache)
  n_new = n - n_len + 1
  if n_new > 0:
    cache = cache + ([0] * n_new)
    for i in range(n_len, n + 1):
      cache[i] = cache[i - 1] * i % mod
    mfactorial.__cache = cache

  return mfactorial.__cache[n]


def cmb(n, r, mod):
  result = mfactorial(n, mod)
  result *= pow(mfactorial(r, mod), mod - 2, mod) % mod
  result %= mod
  result *= pow(mfactorial(n - r, mod), mod - 2, mod) % mod
  result %= mod

  return result


def main():
  MOD = 10 ** 9 + 7

  N, M, K = [int(i) for i in input().strip().split(' ')]
  c = cmb(N * M - 2, K - 2, MOD)

  X = 0
  Y = 0
  for i in range(M):
    X += (M - i) * i
  for i in range(N):
    Y += (N - i) * i

  total = (X * (N ** 2) + Y * (M ** 2)) % MOD * c % MOD
  print(total)


main()
### BUGGY CODE ###

MOD = 10**9+7
k = int(input())
s = input()
n = len(s)

U = n+k
fact = [0]*(U+1)
fact[0] = 1
for i in range(1, U+1):
    fact[i] = fact[i-1]*i % MOD


invfact = [0]*(U+1)
invfact[U] = pow(fact[U], MOD-2, MOD)
for i in reversed(range(U)):
    invfact[i] = invfact[i+1]*(i+1) % MOD


def nCr(n, r):
    if r < 0 or n < r:
        return 0
    return fact[n]*invfact[r]*invfact[n-r]


ans = 0
for x in range(k+1):
    ans += pow(26, x, MOD)*nCr(n+k-x-1, n-1)*pow(25, k-x, MOD)
    ans %= MOD
print(ans)


### FIXED CODE ###

MOD = 10**9+7
k = int(input())
s = input()
n = len(s)


U = n+k
fact = [0]*(U+1)
fact[0] = 1
for i in range(1, U+1):
    fact[i] = fact[i-1]*i % MOD


invfact = [0]*(U+1)
invfact[U] = pow(fact[U], MOD-2, MOD)
for i in reversed(range(U)):
    invfact[i] = invfact[i+1]*(i+1) % MOD


def nCr(n, r):
    if r < 0 or n < r:
        return 0
    return fact[n]*invfact[r]*invfact[n-r]


ans = 0
for x in range(k+1):
    ans += pow(26, x, MOD)*nCr(n+k-x-1, n-1)*pow(25, k-x, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

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

result = [0]*N

for m in range(M):
    L, R = map(int, input().split())
    for i in range(L, R+1):
        result[i-1] += 1

counter = 0
for i in result:
    if i == M:
        counter += 1
print(counter)

### FIXED CODE ###

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

for m in range(M):
    L, R = map(int, input().split())
    if m==0:
        l = L
        r = R
    else:
        if l<L:
            l = L
        if R<r:
            r = R

print(len(list(range(l,r+1))))
### BUGGY CODE ###

from itertools import combinations
n = int(input())
s = input()

explo = list(combinations(range(n),3))

tem = []
for per in explo:
    tem.append(s[per[0]]+s[per[1]]+s[per[2]])

ans = set(tem)


print(len(ans))





### FIXED CODE ###

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

dp = [[0]*10 for _ in range(10)]

count = [0]*10

result = []

for i in range(n-2):
    if count[int(s[i])]==0:
        for j in range(i+1,n-1):
            if dp[int(s[i])][int(s[j])]==0:
                tem = "".join(set(s[j+1:]))
                for k in range(len(tem)):
                    result.append(s[i]+s[j]+tem[k])
                dp[int(s[i])][int(s[j])]=1
        count[int(s[i])]=1

ans = set(result)
print(len(ans))
### BUGGY CODE ###

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

cntli = []
for i in range(q):
    si = s[lr[i][0]-1:lr[i][1]]
    si.strip("G")
    si.strip("C")
    cnt = 0
    for j in range(len(si)-1):
        if si[j] == "A":
            if si[j+1] == "C":
                cnt += 1
    else:
        cntli.append(cnt)

for p in cntli:
    print(p)

### 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 math

Q = int(input())

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

li = []
for i in range(Q):
    l, r = map(int, input().split())
    li.append((l, r))

for l,r in li:
    ans = 0
    for x in range(l, r+1):
        if x % 2 == 1:
            if is_prime(x) and is_prime((x+1)/2):
                ans += 1
    print(ans)

### FIXED CODE ###

import math

Q = int(input())
sosu = [2]

for L in range(3, 10**5, 2): # 2 以外の素数は奇数なので
    for L2 in sosu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosu.append(L)

sosu = set(sosu)

d = {0:0}
now = 0
for x in range(1, 10**5+1):
    if x % 2 == 1:
        if x in sosu and (x+1)/2 in sosu:
            now += 1
    d[x] = now

li = []
for i in range(Q):
    l, r = map(int, input().split())
    li.append((l, r))

for l,r in li:
    ans = 0
    print(d[r]-d[l-1])
### BUGGY CODE ###

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

if N == 1:
    print(1)
    exit()

def saisho_ko_baisu(A,B):
    # A < B
    x = A*B
    r = B%A
    while r!=0:
        B = A
        A = r
        r = B%A
    return x//A

A.sort(reverse = True)
tmp = saisho_ko_baisu(A[0], A[1])
for i in range(2,N):
    if tmp % A[i] != 0:
        tmp = saisho_ko_baisu(A[i], tmp)
res = 0
for a in A:
    res += tmp//a

print(res % (10**9 + 7))


### FIXED CODE ###

from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

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

div = 10**9 + 7
lcm_num = lcm(a)
ans = [lcm_num//ai for ai in a]

print(sum(ans)%div)
### BUGGY CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
aa = [0]
bb = [0]
sub = []
for i in a:
    aa.append(aa[-1]+i)
for i in b:
    bb.append(bb[-1]+i)
for i in range(len(aa)):
    if aa[i] > k:
        break
    for j in range(len(bb)):
        if aa[i]+bb[j] <= k:
            tmp = i+j
    sub.append(tmp)
print(max(sub))


### FIXED CODE ###

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

import fractions
from functools import reduce
N = int(input())
A = list(map(int,input().split()))
#累積GCD
left = [0]
right = [0]
for i in range(N):
  left.append(fractions.gcd(left[i],A[i]))
  right.insert(0,fractions.gcd(right[0],A[N-1-i]))

ans = 0
for i in range(N):
  ans = max(ans,fractions.gcd(left[i],right[i + 1]))
print(ans)

### FIXED CODE ###

import fractions
from functools import reduce
N = int(input())
A = list(map(int,input().split()))
#累積GCD
left = [0]*(N+1)
right = [0]*(N+1)
for i in range(N):
  left[i+1] = (fractions.gcd(left[i],A[i]))
  right[N-i-1] = (fractions.gcd(right[N-i],A[N-1-i]))

ans = 0
for i in range(N):
  ans = max(ans,fractions.gcd(left[i],right[i + 1]))
print(ans)
### BUGGY CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline())
K = list(map(int, sys.stdin.readline().split()))


def solve(k):
    ret = 0
    d = 0
    m = 0
    dm = 0
    l = 0
    r = 0
    while r < N:
        if k <= r:
            if S[l] == 'D':
                d -= 1
                dm -= m
            if S[l] == 'M':
                m -= 1
            l += 1

        if S[r] == 'D':
            d += 1
        if S[r] == 'M':
            m += 1
            dm += d
        if S[r] == 'C':
            ret += dm
        r += 1
    return ret


for k in K:
    ans = solve(k)
    print(ans)


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline())
K = list(map(int, sys.stdin.readline().split()))


def solve(k):
    ret = 0
    d = 0
    m = 0
    dm = 0
    l = 0
    r = 0
    while r < N:
        if k <= r:
            if S[l] == 'D':
                d -= 1
                dm -= m
            if S[l] == 'M':
                m -= 1
            l += 1

        if S[r] == 'D':
            d += 1
        if S[r] == 'M':
            m += 1
            dm += d
        if S[r] == 'C':
            ret += dm
        r += 1
    return ret


for k in K:
    ans = solve(k)
    print(ans)
### BUGGY CODE ###

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

A = []
ans = 0
for i in range(len(P)):
    if ans < sum(P[i:i+K]):
        ans = sum(P[i:i+K])
        A.append(i)
A1 = sorted(A, reverse = True) 
L = A1[0]                
B = P[L:L+K]

C  = []
for i in B:
    C.append(1/2*(i+1))
print(sum(C))

### FIXED CODE ###

from itertools import accumulate

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

A = []
for i in P:
    A.append(1/2*(i+1))
    #A.append(1/2*i*(i+1)/i)

ans = 0
'''
for i in range(len(A)):
    ans = max(ans,sum(A[i:i+K]))
'''
    
accum = [0] + list(accumulate(A))
for i in range(len(accum)):
    ans = max(ans,accum[i] - accum[i-K])
print(ans)