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

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

N, M = LI()
demands = []
for i in range(M):
    demands.append(LI())

demands = sorted(demands, key=lambda x: x[1])
demands_met_flag = [False]*len(demands)

def main():
    counter = 0
    for i in range(len(demands)):
        if demands_met_flag[i] == True: continue
        demand = demands[i]
        demands_met_flag[i] = True
        counter += 1
        deleting_bridge = demand[1]-1
        for j in range(i, len(demands)):
            if demands_met_flag[j] == True: continue
            if demands[j][0] <= deleting_bridge:
                demands_met_flag[j] = True

    print(counter)

main()

### FIXED CODE ###

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

def main():
    N, M = LI()
    demands = []
    for i in range(M):
        demands.append(LI())

    demands = sorted(demands, key=lambda x: x[1])
    demands_met_flag = [False]*len(demands)

    counter = 0
    deleting_bridge = 0
    for i in range(len(demands)):
        if demands_met_flag[i] == True: continue
        if demands[i][0] <= deleting_bridge:
            demands_met_flag[i] = True
            continue
        demand = demands[i]
        demands_met_flag[i] = True
        counter += 1
        deleting_bridge = demand[1]-1

    print(counter)

main()
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
nums = set(a_list)
r_list = []
for n in nums:
	count = a_list.count(n) + a_list.count(n-1) + a_list.count(n+1)
	r_list.append(count)
print(max(r_list))

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
r_list = [0]*(10**5+2)
for n in a_list:
	r_list[n] += 1
	r_list[n+1] += 1
	if n > 0:
		r_list[n-1] += 1
print(max(r_list))
### BUGGY CODE ###

import copy

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

a = [0] + a + [0]

for i in range(n):
  my_sum = 0
  l = copy.copy(a)
  del l[i+1]
  for j in range(n):
    my_sum += abs(l[j] - l[j+1])
  print(my_sum)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

A.insert(0,0)
A.append(0)

S = 0

for i in range(1,N+2):
    S += abs(A[i]-A[i-1])

for i in range(1,N+1):
    print(S + abs(A[i-1]-A[i+1]) - abs(A[i-1]-A[i]) - abs(A[i]-A[i+1]))
### BUGGY CODE ###

import sys
import numpy as np


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w, m = map(int, read().split())
    target = set()
    row = np.zeros(h, dtype=int)
    col = np.zeros(w, dtype=int)
    for _ in range(m):
        hi, wi = [int(i) - 1 for i in input().split()]
        target.add((hi, wi))
        row[hi] += 1
        col[wi] += 1
    r = row.max()
    c = col.max()
    for ri in np.arange(h)[row == r]:
        for ci in np.arange(w)[col == c]:
            if (ri, ci) not in target:
                print(r + c)
                return
    print(r + c - 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w, m = map(int, read().split())
    target = set()
    row = [0] * h
    col = [0] * w
    for _ in range(m):
        hi, wi = [int(i) - 1 for i in input().split()]
        target.add((hi, wi))
        row[hi] += 1
        col[wi] += 1
    row_max = max(row)
    r = [i for i in range(h) if row[i] == row_max]
    col_max = max(col)
    c = [i for i in range(w) if col[i] == col_max]
    for ri in r:
        for ci in c:
            if (ri, ci) not in target:
                print(row_max + col_max)
                return
    print(row_max + col_max - 1)


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

N = int(input())

def f(n):
    flag = False
    #total = 0
    ans = 0
    for x in range(1,100):
        for y in range(1,100):
            for z in range(1,100):
                if (x + y + z)**2 - (x*y + y*z + x*z) == n:
                    #total += 1
                    flag = True
                    break
            if flag:
                break
        if flag:
            break
    if x == 99:
        ans = 0
    elif x == y and  y== z:
        ans = 1
    elif x == y or y == z or x == z:
        ans = 3
    else:
        ans = 6
    return ans

for i in range(1,N+1):
    print(f(i))

### FIXED CODE ###

N = int(input())


ans = [0]*(N+1)
i = 102
for x in range(1,i):
    for y in range(1,i):
        for z in range(1,i):
            total = (x + y + z)**2 - (x*y + y*z + x*z)
            if total <= N:
                ans[total] += 1

for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n = int(input())
    if n%2 == 0:
        print(n//2,n,n)
        return
    for i in range(1,3501):
        for j in range(i + 1,3501):
            if (n * i * j)%(4 * i * j - n * j - n * i) == 0:
                ans = (i ,j , (n * i * j)//(4 * i * j - n * j - n * i))
                break
    
    print(*ans)

if __name__ =='__main__':
    main()  

### FIXED CODE ###

MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n = int(input())
    if n%2 == 0:
        print(n//2,n,n)
        return
    for i in range(1,3501):
        for j in range(i + 1,3501):
            if (n * i * j)%(4 * i * j - n * j - n * i) == 0:
                ans = (i ,j , (n * i * j)//(4 * i * j - n * j - n * i))
                break
    
    print(*ans)

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

import sys
input = sys.stdin.readline

# D - ModSum
n = int(input())
ans = 0

for i in range(n):
	ans += i

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# D - ModSum
n = int(input())

if (n-1) % 2 == 0:
	ans = n * (n-1)//2
else:
	ans = (n-1) * n//2

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

n = int(input())

d = [1]*n

for i in range(2, n+1):
    k = 1
    while i*k <= n:
        d[i*k-1] += 1
        k += 1

ans = 0
for i in range(n):
    ans += (i+1)*d[i]

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n+1):
  d = n // i
  ans += d*(d+1)//2*i
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []
y = 0
for x in range(1, 1001):
    y += x
    l.append(y/x)
m = []
for i in p:
    m.append(l[i-1])
s = [0]
z = 0
for i in m:
    z += i
    s.append(z)
ans = []
for i in range(n-k+1):
    a = p[i:i+k]
    ans.append(s[i+k] - s[i])
print(max(ans))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []
y = 0
for x in range(1, 1001):
    y += x
    l.append(y/x)
m = []
for i in p:
    m.append(l[i-1])
s = [0]
z = 0
for i in m:
    z += i
    s.append(z)
ans = 0
for i in range(n-k+1):
    ans = max(ans, s[i+k] - s[i])
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(6009)
from collections import defaultdict
dp=defaultdict(lambda:"")

s=input()
n=len(s)
t=input()
m=len(t)
def lcs(x,y):
	if min(x,y)<=-1:
		return ""
	if dp[(x,y)]!="":
		return dp[(x,y)]
	if s[x]==t[y]:
		dp[(x,y)]=lcs(x-1,y-1)+s[x]
		return dp[(x,y)]
	a=lcs(x-1,y)
	b=lcs(x,y-1)
	if len(a)>len(b):
		dp[(x,y)]=a
		return a
	else:
		dp[(x,y)]=b
		return b
print(lcs(n-1,m-1))

### FIXED CODE ###

s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1,n+1):
	for j in range(1,m+1):
		if s[i-1]==t[j-1]:
			dp[i][j]=dp[i-1][j-1]+1
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
i=n
j=m
st=""
while dp[i][j]:
	while dp[i-1][j]==dp[i][j]:
		i-=1
	while dp[i][j-1]==dp[i][j]:
		j=j-1
	j-=1
	st+=s[i-1]
	i-=1
print(st[::-1])
### BUGGY CODE ###

num = int(input())
suzi = list(map(int,input().split()))
ans = 1
for kazu in suzi:
	ans *= kazu
if ans >  1000000000000000000:
	print(-1)
else:
	print(ans)

### FIXED CODE ###

def main():
    num = int(input())
    suzi = list(map(int,input().split()))

    if 0 in suzi:
	    print(0)
	    return
    ans = 1
    for kazu in suzi:
        ans *= kazu
        if ans > 1000000000000000000:
            print(-1)
            return
    print(ans)


main()
### BUGGY CODE ###

"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(W, w-1, -1):
            if (dp[i] < (dp[i-w] + v)):
                dp[i] = dp[i-w] + v
        #print(dp,sep="\n")

    #4:出力
    print(max(dp))

if __name__ == '__main__':
    main()

### FIXED CODE ###

"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(W, w-1, -1):
            tmp = dp[i-w] + v
            if dp[i] < tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    print(max(dp))

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

H,K=map(int,input().split())

ln=list(map(int,input().split()))

sum=0

if K!=0:
	for A in range(K):
  		ln[ln.index(max(ln))]=0

for A in ln:
  sum+=A

print(sum)

### FIXED CODE ###

H,K=map(int,input().split())
 
s=list(map(int,input().split()))
 
sum=0

s.sort(reverse=True)

if K>=len(s):
  for A in range(len(s)):
    s[A]=0

else:
  for A in range(K):
    s[A]=0



for A in s:
  sum+=A
 
print(sum)
### BUGGY CODE ###

n = int(input())

unique_list = list()
for _ in range(n):
    s = input()
    if s not in unique_list:
        unique_list.append(s)

print(len(unique_list))


### FIXED CODE ###

n = int(input())

gacha_set = set()
for _ in range(n):
    s = input()
    gacha_set.add(s)

print(len(gacha_set))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, Q = list(map(int, input().split()))
nodes = {i:[] for i in range(N)}
for i in range(N-1):
  r, e = list(map(int, input().split()))
  r, e = r - 1, e - 1
  nodes[r].append(e)
  nodes[e].append(r)
#print(nodes)

result = [0] * N
for i in range(Q):
  r, s = list(map(int, input().split()))
  result[r-1] += s

def dfs(r, prev=-1):
  for i in nodes[r]:
    if i != prev:
      result[i] += result[r]
      dfs(i, r)

dfs(0)
print(" ".join(map(str, result)))

### FIXED CODE ###

#人の（ほぼ同じなのにうまくいかないので）
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
lines = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    lines[a-1].append(b-1)
    lines[b-1].append(a-1)
ans = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(v, parent):
    for u in lines[v]:
        if u != parent:
            ans[u] += ans[v]
            dfs(u, v)

dfs(0, -1)
print (*ans)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    S = input()[::-1]
    L = len(S)
    dp = [0] * 2019
    wk = 0
    for i in range(L):
        wk = (int(S[i])*(10**i) + wk)%2019
        dp[wk] += 1
    ret = dp[0]
    for i in range(2019):
        ret += dp[i]*(dp[i]-1)//2
    print(ret)


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    S = input()[::-1]
    L = len(S)
    dp = [0] * 2019
    wk = 0
    r = 1
    for i in range(L):
        wk += int(S[i])*r
        wk %= 2019
        r *= 10
        r %= 2019
        dp[wk] += 1
    ret = dp[0]
    for i in range(2019):
        ret += dp[i]*(dp[i]-1)//2
    print(ret)


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

N = int(input())
L = list(map(int,input().split()))
ans = 0
for i in range(N):
    Pi = L[i]
    tes = True
    for j in range(i + 1):
        if Pi > L[j]:
            tes = False
    if tes:
        ans +=1 
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read#全部読み込むやつ
readline = sys.stdin.buffer.readline#1行読み込むやつ
readlines = sys.stdin.buffer.readlines#リストで読み込むらしい


N,*L = map(int,read().split())
ans = 0
Pj = L[0]
for i in L:
    Pj = min(Pj,i)    
    if Pj >= i:
        ans += 1
print(ans)
### BUGGY CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z==s:
        cnt+=1
print(cnt)

### FIXED CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
  for y in range(k+1):
      if (s-(x+y)>=0)and(s-(x+y)<=k):
        cnt+=1
print(cnt)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    s = LI()
    t = LI()
    a = [[0] * m for _ in range(n)]
    u = [[0] * m for _ in range(n)]
    for i in range(n):
        b = s[i]
        c = a[i]
        d = u[i-1]
        for j in range(m):
            if b != t[j]:
                continue
            k = 1
            if i>0 and j>0:
                k += d[j-1]
            c[j] = k
        e = u[i] = c[:]
        for j in range(1,m):
            e[j] += e[j-1]
            e[j] %= mod
        if i > 0:
            for j in range(m):
                e[j] += d[j]
                e[j] %= mod

    r = sum(map(lambda x: sum(x) % mod, a)) + 1
    r %= mod

    return r


print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    s = LI()
    t = LI()
    a = [[1 if i==j else 0 for j in t] for i in s]
    u = [0] * m
    for i in range(n):
        c = a[i]

        for j in range(1,m):
            if c[j] == 1:
                c[j] += u[j-1]

        e = c[:]
        for j in range(1,m):
            e[j] += e[j-1]
            e[j] %= mod

        if i > 0:
            for j in range(m):
                e[j] += u[j]
                e[j] %= mod
        u = e

    r = sum(map(lambda x: sum(x) % mod, a)) + 1

    return r % mod


print(main())
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

sN = []
sQ = []
Q = 0
N = 0


def gor(pos):
    for i in range(Q):
        if sN[pos] == sQ[i]['t']:
            if sQ[i]['d'] == 'R':
                pos = pos + 1
            else:
                pos = pos - 1

            if pos < 0:
                return False
            if pos > N - 1:
                return True

    return False


def getr():
    l = 0
    r = N - 1
    res = N
    while r >= l:
        mid = (l + r) // 2
        if gor(mid):
            res = mid
            r = mid - 1
        else:
            l = mid + 1
    return res


def gol(pos):
    for i in range(Q):
        if sN[pos] == sQ[i]['t']:
            if sQ[i]['d'] == 'L':
                pos = pos - 1
            else:
                pos = pos + 1

            if pos > N - 1:
                return False
            if pos < 0:
                return True

    return False


def getl():
    l = 0
    r = N - 1
    res = -1
    while l <= r:
        mid = (l + r) // 2
        if gol(mid):
            res = mid
            l = mid + 1
        else:
            r = mid - 1
    return res


if __name__ == '__main__':
    N, Q = map(int, input().split())  # N, Q for number

    sN = input()  # squares

    for i in range(0, Q):
        t, d = input().split()
        sQ.append({'t': t, 'd': d})

    removed_l = getl() + 1
    removed_r = N - getr()

    print(N - removed_l - removed_r)


### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

sN = []
sQ = []
dQ = []
Q = 0
N = 0


def gor(pos):
    for i in range(Q):
        if sN[pos] == sQ[i]:
            if dQ[i] == 'R':
                pos = pos + 1
            else:
                pos = pos - 1

            if pos < 0:
                return False
            if pos > N - 1:
                return True

    return False


def getr():
    l = 0
    r = N - 1
    res = N
    while r >= l:
        mid = (l + r) // 2
        if gor(mid):
            res = mid
            r = mid - 1
        else:
            l = mid + 1
    return res


def gol(pos):
    for i in range(Q):
        if sN[pos] == sQ[i]:
            if dQ[i] == 'L':
                pos = pos - 1
            else:
                pos = pos + 1

            if pos > N - 1:
                return False
            if pos < 0:
                return True

    return False


def getl():
    l = 0
    r = N - 1
    res = -1
    while l <= r:
        mid = (l + r) // 2
        if gol(mid):
            res = mid
            l = mid + 1
        else:
            r = mid - 1
    return res


if __name__ == '__main__':
    N, Q = map(int, input().split())  # N, Q for number

    sN = input()  # squares

    for i in range(0, Q):
        t, d = input().split()
        sQ.append(t)
        dQ.append(d)
        #sQ.append({'t': t, 'd': d})

    removed_l = getl() + 1
    removed_r = N - getr()

    print(N - removed_l - removed_r)
### BUGGY CODE ###

mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in list(s):
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
result = 0
for i in range(1, 2**len(d)):
    c = 1
    num = i
    for n, j in d.items():
        if num%2==1:
            c = (c*j)%mod
        num >>= 1
    result = (result+c)%mod

print(result%mod)

### FIXED CODE ###

mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in s:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
result = 1
for i, j in d.items():
    result = (result*(j+1))%mod

print((result-1)%mod)
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]

S_set = set(S)
Cnt = []
max = 0
for i in S_set:
    Cnt.append([i, S.count(i)])
    if max < S.count(i):
        max = S.count(i)

Cnt_l = sorted(Cnt, reverse = False , key=lambda x: x[0])
#print(Cnt_l)
#print(max)
for i in range(len(Cnt_l)):
    if Cnt_l[i][1] == max:
        print(Cnt_l[i][0])

### FIXED CODE ###

from collections import Counter

N = int(input())
S = [input() for i in range(N)]

c = Counter(S)
max_c = max(c.values())
#キーの昇順でソート
c_sorted = sorted(c.items(), key = lambda x:x[0])
for v in c_sorted:
    if v[1] == max_c:
        print(v[0])
### BUGGY CODE ###

n=int(input())
s=[list(input()) for _ in range(n)]
ss=[si+si for si in s]
ss=ss+ss
ans=0
for i in range(n):
  for j in range(n):
    a=[si[j:j+n] for si in ss[i:i+n]]
    flg=True
    for k in range(n-1):
      a1=a[k][k+1:]
      a2=[a[i+1][k] for i in range(k,n-1)]
      if a1!=a2:
        flg=False
        break
    if flg:ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=[list(input()) for _ in range(n)]
import numpy as np
ss=[si+si for si in s]
ss=np.array(ss+ss)
ans=0
for i in range(n):
    a=ss[i:i+n,:n]
    if np.array_equal(a,a.T):
      ans+=1
print(ans*n)
### BUGGY CODE ###

MOD = (10 ** 9) + 7

N = int(input())
s = list(input())

dp = [[0 for i in range(N + 1)] for j in range(N + 1)]


for i in range(N + 1):
	dp[i][i] = 1
for i in range(N):
	dp[i][i + 1] = 1

for n in range(1, N + 1):
	dp[n][0] = (dp[n - 1][0] + 2 * dp[n - 1][1]) % MOD
	for l in range(1, n):
		dp[n][l] = (dp[n - 1][l - 1] + 2 * dp[n - 1][l + 1]) % MOD

print(dp[N - 1][len(s)])

### FIXED CODE ###

MOD = (10 ** 9) + 7

N = int(input())
s = list(input())

dp = [[0] * (N + 2) for i in range(N + 1)]

for n in range(N + 1):
	for l in range(n + 1):
		if n == 1:
			dp[n][l] = 1
		elif l == 0:
			dp[n][l] = (dp[n - 1][0] + 2 * dp[n - 1][1]) % MOD
		else:
			dp[n][l] = (dp[n - 1][l - 1] + 2 * dp[n - 1][l + 1]) % MOD

print(dp[N][len(s)])
### BUGGY CODE ###

# import sys
# input = sys.stdin.readline
import itertools


# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    n, k = input_list()
    a = input_list()
    ans = 0
    for i in range(n-k+1):
        kitai = list(map(lambda x: (x+1)/2, a[i:i+k]))
        ans = max(ans, sum(kitai))
    print(ans)


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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

def kitai(x):
  return (1+int(x))/2

p = list(map(kitai, input().split()))

pre = psum = sum(p[0:k])

for i in range(1, n):
  if i+k > n:
    break
  pre = pre - p[i-1] + p[i+k-1]
  psum = max(psum, pre)

print(psum)