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

if __name__ == '__main__':
    n, k = [int(i) for i in input().split(" ")]
    while abs(n - k) <= n:
        if n%(k*10)==0:
            n = int(n/(k*10))
        else:
            n = abs(n - k)
        
    print(n)

### FIXED CODE ###

if __name__ == '__main__':
    n, k = [int(i) for i in input().split(" ")]
    while abs(n - k) < n and n != 0:
        n = n%k
        if n != 0:
            n = abs(n - k)
    print(n)
### BUGGY CODE ###

#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([0,i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

inf=float("inf")
 
t=[[inf for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[1]][txy[2]]=0

count=0
while q:
    d,y,x=q.pop(0)
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==inf:
            t[ny][nx]=t[y][x]+1
            q.append([d+1,ny,nx])
    if d==h+w:
        break
print(d)

### FIXED CODE ###

#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

from collections import deque

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

t=[[-1 for _ in range(w)] for _ in range(h)]
q=deque()
for txy in sxy:
    q.append(txy)
    t[txy[0]][txy[1]]=0

count=0
while q:
    y,x=q.popleft()
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==-1:
            t[ny][nx]=t[y][x]+1
            q.append([ny,nx])
a=0
for i in range(h):
    for j in range(w):
        a=max(a,t[i][j])
print(a)
### BUGGY CODE ###

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
w=[items[i][0] for i in range(n)]
v=[items[i][1] for i in range(n)]

memo=[[-1]*(W+1) for i in range(n+1)]
def dfs(i,j):
  if i==n:
    return 0
  if memo[i][j]!=-1:
    return memo[i][j]
  else:
    if  j<w[i]:
      return dfs(i+1,j)
    else:
      return max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])
print(dfs(0,W))

### FIXED CODE ###

import sys
input=sys.stdin.readline

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
import numpy as np

dp=np.zeros([n+1,W+1],dtype=np.int64)
for i in range(n):
  w=items[i][0]
  v=items[i][1]
  dp[i+1][:w]=dp[i][:w]
  dp[i+1][w:]=np.maximum(dp[i][w:],dp[i][:-w]+v)
print(dp[-1][-1])
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    class segTree:
        def __init__(self,n):
            if bin(n).count("1") == 1:
                self.leaves = 2**(n.bit_length()-1)
            else:
                self.leaves = 2**n.bit_length()
            self.identity = set()
            self.tree = [self.identity]*(self.leaves*2)

        def merge(self,x,y):
            #ここにマージ処理を書く
            return x | y

        def update(self,i,x):
            i = i+self.leaves
            self.tree[i] = set(x)
            i >>= 1
            while i > 0:
                self.tree[i] = self.merge(self.tree[i*2],self.tree[i*2+1])
                i >>= 1

        def query(self,l,r):
            #[l:r)のクエリ結果を返す
            l = l + self.leaves
            r = r + self.leaves
            res = self.identity
            while l < r:
                if l&1:
                    res = self.merge(res,self.tree[l])
                    l += 1
                if r&1:
                    r -= 1
                    res = self.merge(res,self.tree[r])
                l >>= 1
                r >>= 1
            return res
    N = int(input())
    st = segTree(N)
    S = input()
    Q = int(input())
    for i in range(N):
        st.update(i,S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            st.update(int(a)-1,b)
        else:
            print(len(st.query(int(a)-1,int(b))))
main()


### FIXED CODE ###

"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    class BIT:
        def __init__(self,n):
            self.size = n
            self.tree = [Counter([]) for _ in range(n+1)]
        
        def change(self,i,x,y):
            while i <= self.size:
                if x in self.tree[i]:
                    self.tree[i][x] -= 1
                if y not in self.tree[i]:
                    self.tree[i][y] = 1
                else:
                    self.tree[i][y] += 1
                i += i&-i
    
        def sum(self,i):
            s = Counter([])
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            cnt = 0
            return s


    N = int(input())
    S = list(input())
    Q = int(input())
    bit = BIT(N)
    for i in range(N):
        bit.change(i+1," ",S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            x = S[int(a)-1]
            S[int(a)-1] = b
            bit.change(int(a),x,b)
        else:
            a = int(a)
            b = int(b)
            count = bit.sum(b) - bit.sum(a-1)
            ans = 0
            for v in count.values():
                if v > 0:
                    ans += 1
            print(ans)
main()
### BUGGY CODE ###

import sys

import numpy as np


def search_y(x, points):
    l = np.complex128(x + 0.0j)
    r = np.complex128(x + 1000.0j)

    d1, d2 = 0, 0
    while abs(r - l) > 3e-7:
        diff = (l + r) / 3
        p1 = l + diff
        p2 = l + diff * 2
        d1 = abs(points - p1).max()
        d2 = abs(points - p2).max()
        if d1 >= d2:
            l = p1
        else:
            r = p2
    return (d1 + d2) / 2


def search(points):
    l = 0.0
    r = 1000.0

    d1, d2 = 0, 0
    while r - l > 3e-7:
        diff = (r - l) / 3
        p1 = l + diff
        p2 = l + diff * 2
        d1 = search_y(p1, points)
        d2 = search_y(p2, points)
        if d1 >= d2:
            l = p1
        else:
            r = p2
    return (d1 + d2) / 2


n = int(input())
points = np.array([complex(*map(int, line.split())) for line in sys.stdin], dtype=np.complex128)
print(search(points))


### FIXED CODE ###

import sys
from itertools import combinations

import numpy as np

n = int(input())
points = np.array([np.fromiter(map(int, line.split()), dtype=np.float64) for line in sys.stdin])

if n == 2:
    p1, p2 = points
    print(np.sqrt(((p1 - p2) ** 2).sum()) / 2)
    exit()

ans = 10 ** 18
for p1, p2, p3 in combinations(points, 3):
    A = ((p2 - p3) ** 2).sum()
    B = ((p3 - p1) ** 2).sum()
    C = ((p1 - p2) ** 2).sum()
    sa, sb, sc = sorted([A, B, C])
    if sa + sb <= sc + 1e-7:
        c = (p2 + p3 if A == sc else p1 + p3 if B == sc else p1 + p2) / 2
        R2 = sc / 4
    else:
        T = A * (B + C - A)
        U = B * (C + A - B)
        W = C * (A + B - C)
        c = (T * p1 + U * p2 + W * p3) / (T + U + W)
        R2 = ((c - p1) ** 2).sum()
    if ((points - c) ** 2).sum(axis=1).max() <= R2 + 1e-7:
        print(np.sqrt(R2))
        break
else:
    raise AssertionError
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())

neighbor = [[] for _ in range(n + 1)]

for i in range(n - 1):
    x, y = map(int, input().split())
    neighbor[y].append(x)
    neighbor[x].append(y)

mod = 10**9 + 7
dp = [[0] * 2 for _ in range(n + 1)]


def dfs(i, bw, p):
    if dp[i][bw] != 0:
        return dp[i][bw]

    dp[i][bw] = 1
    for j in neighbor[i]:
        if j == p:
            continue

        if bw == 0:  # black
            dp[i][0] = (dp[i][0] * dfs(j, 1, i)) % mod
        else:  # white
            dp[i][1] = (dp[i][1] * (dfs(j, 0, i) + dfs(j, 1, i))) % mod

    return dp[i][bw]


print((dfs(1, 0, 0) + dfs(1, 1, 0)) % mod)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())

neighbor = [[] for _ in range(n + 1)]

for i in range(n - 1):
    x, y = map(int, input().split())
    neighbor[y].append(x)
    neighbor[x].append(y)

mod = 10**9 + 7
dp = [[0] * 2 for _ in range(n + 1)]


def dfs(i, bw, p):
    if dp[i][bw] != 0:
        return dp[i][bw]

    dp[i][bw] = 1
    for j in neighbor[i]:
        if j == p:
            continue

        if bw == 0:  # black
            dp[i][0] = (dp[i][0] * dfs(j, 1, i)) % mod
        else:  # white
            dp[i][1] = (dp[i][1] * (dfs(j, 0, i) + dfs(j, 1, i))) % mod

    return dp[i][bw]


print((dfs(1, 0, 0) + dfs(1, 1, 0)) % mod)
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(10**6)

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

P = [0]*n
for i in range(q):
  p,x = map(int,input().split())
  P[p-1] += x
     
def dfs(v,pv):      
  for nv in G[v]:
    if nv != pv:
      P[nv] += P[v]
      dfs(nv,v)
        
dfs(0,0)
print(*P)

### FIXED CODE ###

from collections import deque

n,q = map(int,input().split())
cnt = [0]*(n+1)
g=[[] for _ in range(n+1)]

for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
  
for _ in range(q): 
  v,val=map(int,input().split())
  cnt[v]+=val    
  
q = deque()
q.append(1)
checked = [0]*(n+1) 
while q:
  v = q.pop()
  checked[v] = 1
  for vc in g[v]:
    if checked[vc] == 1:
      continue
    else:
      cnt[vc] += cnt[v]
      q.append(vc)
    
print(*cnt[1:])
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()
H = LI()

dp = [mod for i in range(N)]
dp[0] = 0
for i in range(N):
    for j in range(min(K + 1, N - i)):
        # print(i, j)
        dp[i+j] = min(dp[i] + abs(H[i] - H[i + j]), dp[i+j])

print(dp[-1])

### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()
H = LI()

dp = [mod for i in range(N)]
dp[0] = 0
for i in range(N):
    for j in range(min(K + 1, N - i)):
        # print(i, j)
        dp[i+j] = min(dp[i] + abs(H[i] - H[i + j]), dp[i+j])

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

import sys
import math
#import fractions
from functools import reduce
import itertools

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'
def euclid(a, b):
    while b:
        a, b = b, a%b
    return a
# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

def gcd_list(numbers):
    return reduce(euclid, numbers)

def a(x):
    ans = x[0]
    for i in range(1, len(x)):
        ans = fractions.gcd(ans, x[i])
    return ans

N = II()
l = []
for i in range(1,N+1):
    l.append(i)
ans=0

num = 3 #生成するビット数
bit_list = list(itertools.product(l, repeat=num))

for L in bit_list:
    ans += gcd_list(L)
print(ans)


### FIXED CODE ###

import sys
#import fractions
from math import gcd
import itertools

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

def gcd_list(numbers):
    return reduce(gcd, numbers)

def euclid(p,q):
    if p%q==0:
        return q
    else:
        return euclid(q,p%q)


N = II()

ans=0

for i in range(1, N+1):
    for j in range(1, N+1):
        x = gcd(i,j)
        for k in range(1, N+1):
            ans+=gcd(x,k)


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

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

ans = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                ans += 1
print(ans)

### FIXED CODE ###

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

ans = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if 0 <= z <= K:
            ans += 1
print(ans)
### BUGGY CODE ###

def main():
    N, T = map(int, input().split())
    ab = [tuple(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: x[0])
    t = ab[-1][0]
    dp = [-1]*(T+t+1)
    dp[0] = 0
    for a, b in ab:
        for i in range(T-1, -1, -1):
            if dp[i] < 0:
                continue
            dp[i+a] = max(dp[i+a], dp[i]+b)
    ans = max(dp)
    print(ans)


main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N, T = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: (x[0], x[1]))
    dp = [-1 for i in range(T*2 + 1)]
    dp[0] = 0
    for a, b in ab:
        for i in range(T*2, 0, -1):
            if i >= a:
                if dp[i-a] >= 0 and i - a < T:
                    dp[i] = max(dp[i], dp[i-a] + b)

    for i in range(1, T*2+1):
        dp[i] = max(dp[i], dp[i-1])
    ans = dp[-1]

    ab.sort(key=lambda x: x[1])
    tmp = ab.pop()
    dp = [-1 for i in range(T)]
    dp[0] = 0
    for a, b in ab:
        for i in range(T-1, 0, -1):
            if i >= a:
                if dp[i-a] >= 0:
                    dp[i] = max(dp[i], dp[i-a] + b)

    for i in range(1, T):
        dp[i] = max(dp[i], dp[i-1])
    ans = max(ans, tmp[1] + dp[-1])

    # print(dp)
    print(ans)


main()
### BUGGY CODE ###

import heapq
N,M = map(int,input().split())
l = [tuple(map(int,input().split())) for _ in range(N)]
l = sorted(l)
heap = []
a = 0
b = 0
for i in range(1,M+1):
        while l and l[a][0] <= i:
            heapq.heappush(heap, -(l[a][1]))
        if heap :
            b -= (heapq.heappop(heap))
print(b)








### FIXED CODE ###

import heapq
N,M = map(int,input().split())
l = [tuple(map(int,input().split())) for _ in range(N)]
l = sorted(l,reverse=True)
heap = []
ans = 0
for i in range(1,M+1):
        while l and l[-1][0] == i:
            heapq.heappush(heap, (l.pop()[1]*(-1)))
        if heap :
            ans -= (heapq.heappop(heap))
print(ans)
### BUGGY CODE ###

# 整数を一つ入力
N = int(input())

# 文字列を一つ入力
S = input()

res = 0

R = []
G = []
B = []

for i in range(N):
    if S[i] == "R":
        R.append(i)
        continue
    if S[i] == "G":
        G.append(i)
        continue
    B.append(i)

for i in R:
    for j in G:
        for k in B:
            if abs(j-i) == abs(k-j) or abs(k-i) == abs(k-j) or abs(k-i) == abs(i-j):
                continue
            res += 1

print(res)


### FIXED CODE ###

# 整数を一つ入力
N = int(input())

# 文字列を一つ入力
S = input()

res = 0

R = []
G = []
B = []

for i in range(N):
    if S[i] == "R":
        R.append(i)
        continue
    if S[i] == "G":
        G.append(i)
        continue
    B.append(i)

BN = len(B)

for i in R:
    for j in G:
        res += BN
        ii,jj = i,j
        if ii > jj:
            ii,jj = jj,ii
        if ii - (jj-ii) >= 0:
            if S[ii-(jj-ii)] == "B":
                res -= 1
        if (abs(jj-ii)) % 2 == 0:
            if S[(jj+ii) // 2] == "B":
                res -= 1
        if jj + (jj-ii) <= N-1:
            if S[jj+(jj-ii)] == "B":
                res -= 1
print(res)
### BUGGY CODE ###

N, K, *A = map(int, open(0).read().split())
S = [1]*(N+1)
for i in range(N):
    if K + i <= N:
        for j in range(i, K + i):
            S[i] *= A[j]
        if i > 0:
            if S[i] > S[i - 1]:
                print("Yes")
            else:
                print("No")
    else:
        exit


### FIXED CODE ###

N, K, *A = map(int, open(0).read().split())
for i in range(N):
    unko = A[i]
    if i + K < N:
        S = A[i + K]
        if S > unko:
            print("Yes")
        else:
            print("No")
    else:
        exit
### BUGGY CODE ###

n, c, k = map(int, input().split())
t = []
for i in range(n):
  t.append(int(input()))
t.sort()
result = 1
count = 0

for i in range(n):
  if (t[count] - t[0]) > k or c == count:
    result += 1
    t = t[count:]
    count = 1
  else:
    count += 1
print(result)

### FIXED CODE ###

n, c, k = map(int, input().split())
t = [int(input()) for i in range(n)]
t.sort()

result = 1
count = 0
f = 0

for i in range(n):
  if (t[i] - t[f]) > k or c == count:
    result += 1
    count = 1
    f = i
  else:
    count += 1
print(result)
### BUGGY CODE ###

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

# BFSで各点から到達可能な最も遠いところを探索する
# 1回探索はO(HW)なのでO(HHWW)
# BFSなのでdeque / queue使う・・・微妙に1つだけTLE残る

# 全ての地点から全ての地点への最短経路を求める

# from collections import deque
import queue

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

data = [None] * H
for i in range(H):
    data[i] = input()


def judge(h, w, dist):
    if (h < 0) or (h >= H) or (w < 0) or (w >= W):
        return False
    if data[h][w] == '#' or dist[h][w] > -1:
        return False
    else:
        return True


def bfs(h, w):
    dist = [[-1] * W for i in range(H)]
    # q = deque()
    q = queue.Queue()

    max_dist = 0
    dist[h][w] = 0
    # q.append((h, w, 0))
    q.put((h, w, 0))

    # while len(q) > 0:
    while not q.empty():
        # h, w, val = q.popleft()
        h, w, val = q.get()
        dist[h][w] = val
        max_dist = max(max_dist, val)

        if judge(h+1, w, dist):
            q.put((h+1, w, val+1))
        if judge(h-1, w, dist):
            q.put((h-1, w, val+1))
        if judge(h, w+1, dist):
            q.put((h, w+1, val+1))
        if judge(h, w-1, dist):
            q.put((h, w-1, val+1))

    return max_dist


ans = 0
for h in range(H):
    for w in range(W):
        if data[h][w] == '.':
            res = bfs(h, w)
            ans = max(ans, res)

print(ans)


### FIXED CODE ###

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

# BFSで各点から到達可能な最も遠いところを探索する
# 1回探索はO(HW)なのでO(HHWW)
# BFSなのでdeque / queue使う・・・微妙に1つだけTLE残る

# 全ての地点から全ての地点への最短経路を求める

'''
3 5
...#.
.#.#.
.#...
'''

import sys
from collections import deque

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = na()
# data = [ns() for _ in range(H)]

data = [list("#" * (W + 2))]
# 周りを'#'で埋めておく
for _ in range(H):
    data.append(["#"] + list(input()) + ["#"])
data += [list("#" * (W + 2))]


def bfs(h, w):
    dist = [[-1] * (W+2) for _ in range(H+2)]
    q = deque()

    max_dist = 0
    dist[h][w] = 0
    q.append((h, w, 0))

    # while len(q) > 0:
    while len(q) > 0:
        h, w, val = q.popleft()

        m = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for dx, dy in m:
            h_new, w_new = h + dx, w + dy
            if data[h_new][w_new] == '.' and dist[h_new][w_new] == -1:
                q.append((h_new, w_new, val+1))
                dist[h_new][w_new] = val + 1
                max_dist = max(max_dist, val + 1)

    return max_dist


ans = 0
for h in range(H+2):
    for w in range(W+2):
        if data[h][w] == '.':
            res = bfs(h, w)
            if ans < res:
                ans = res

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

N,K=map(int, input().split())
L=list(map(int, input().split()))
sumL=[]

for j in range(N):
  L[j]=(1+L[j])*L[j]/2/L[j]
  
def sumlist(a):
  return sum(L[0:a])

for i in range(N-K+1):
  sumL.append(sumlist(i+K)-sumlist(i))
  
print(max(sumL))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
q = [0]
m = 0
for i in p:
    m += (1+i)/2
    q.append(m)
ans = 0
for i in range(k, n+1):
    ans = max(q[i]-q[i-k], ans)

#あまり深く事を考えずに
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

# coding: utf-8 
# Your code here! 
H,W=map(int,input().split()) 
S=[] 

for _ in range(H):
    S.append(list(input()))


def dfs(h,w,num):
    if h==H-1 and w==W-1:
        ans.append(num)
    
    if h!=H-1: 
        if S[h+1][w]=="#": 
            dfs(h+1,w,num+1)
        else:
            dfs(h+1,w,num)

    if w!=W-1: 
        if S[h][w+1]=="#": 
            dfs(h,w+1,num+1)
        else:
            dfs(h,w+1,num)

ans=[]
dfs(0,0,1) if S[0][0]=="#" else dfs(0,0,0)

print(min(ans))



### FIXED CODE ###

# coding: utf-8
# Your code here!
H,W=map(int,input().split())

meizu=[]
for _ in range(H):
    meizu.append(list(input()))

dp=[[10**9 for w in range(W)] for h in range(H)]
dp[0][0]=1 if meizu[0][0]=="#" else 0

for h in range(H):
    for w in range(W):
        if h!=H-1:
            dp[h+1][w]=min(dp[h+1][w],dp[h][w]+1 if meizu[h+1][w]=="#" and meizu[h][w]=="." else dp[h][w])
        if w!=W-1:
            dp[h][w+1]=min(dp[h][w+1],dp[h][w]+1 if meizu[h][w+1]=="#" and meizu[h][w]=="." else dp[h][w])
    
print(dp[-1][-1])
### BUGGY CODE ###

import os, sys, re, math

N, M = [int(s) for s in input().split(' ')]

cards = [int(s) for s in input().split(' ')]
cards.sort()

bc_ary = []
for i in range(M):
    bc_ary.append([int(s) for s in input().split(' ')])

for bc in bc_ary:
    cnt = 0
    idx = 0
    while idx < N and cnt < bc[0]:
        mincard = min(cards)
        if mincard >= bc[1]:
            break
        if mincard < bc[1]:
            cards[cards.index(mincard)] = bc[1]
            cnt += 1
        idx += 1

print(sum(cards))


### FIXED CODE ###

import os, sys, re, math, heapq

N, M = [int(s) for s in input().split(' ')]

dic = {}
cards =  [int(s) for s in input().split(' ')]
for c in cards:
    if c in dic:
        dic[c] += 1
    else:
        dic[c] = 1

for i in range(M):
    b,c = [int(s) for s in input().split(' ')]
    if c in dic:
        dic[c] += b
    else:
        dic[c] = b

keys = sorted(list(dic.keys()), reverse=True)

ret = 0
for k in keys:
    ret += min(N, dic[k]) * k
    N = N - dic[k]
    if N <= 0:
        break

print(ret)
### BUGGY CODE ###


N,K =map(int,input().split())
n = 0
ans = 0
L = K-1
R = N
while True:
    if L < N:
        break
    else:
        n += 1
        R = L
        L = R//2

if R > N:
    R=N

while True:
    foo = R-L
    foo /= 2**n
    ans += foo
    if L==1:
        ans += 1/(2**(n+1))
        break
    R = L
    L =R//2
    n += 1
print(ans/N)

### FIXED CODE ###


N,K =map(int,input().split())
n = 0
ans = 0
L = K-1
R = N
while True:
    if L < N:
        break
    else:
        n += 1
        R = L
        L = R//2

if R > N:
    R=N

while True:
    foo = R-L
    foo /= 2**n
    ans += foo
    if L==1:
        ans += 1/(2**(n+1))
        break
    if L ==0:
        break
    R = L
    L =R//2
    n += 1
print(ans/N)