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

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

scope_index = -1
max_sum = 0
for p_i in range(len(p_list)):
    now_sum = 0
    for i in range(k):
        if len(p_list) <= (p_i + i):
            break
        now_sum += p_list[p_i + i]

    if max_sum < now_sum:
        max_sum = now_sum
        scope_index = p_i

max_scope_list = []
for i in range(k):
    max_scope_list.append(p_list[scope_index + i])

ex = 0
for scope in max_scope_list:
    for num in range(1, scope+1):
        ex += num*1/scope
print(ex)


### FIXED CODE ###

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

scope_index = 0
max_sum = 0
for i in range(k):
    max_sum += p_list[i]

now_sum = max_sum
for p_i in range(k, len(p_list)):
    now_sum -= p_list[p_i - k]
    now_sum += p_list[p_i]

    if max_sum < now_sum:
        scope_index = p_i
        max_sum = now_sum

ex = (max_sum+k)/2
print(ex)
### BUGGY CODE ###

import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = reversed(input().strip())

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
range10 = range(10)
range13 = range(13)
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for s in S:
    if s == '?':
        for d in range10:
            m = mod13_list[(d * mul)]
            for pm in range13:
                dp[mod13_list[(pm+m)]] += dp_[pm]

    else:
        si = int(s)
        m = mod13_list[(si * mul)]
        for pm in range13:
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for i in range13:
        dp_[i] = dp[i] % divisor
        dp[i] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5])

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

s = input()
i = 0
while i <= len(s)-5:
  if len(s)-i >= 7:
    if s[i:i+5] == 'dream':
      if s[i+4:i+6] == 'er':
        i += 7
      else:
        i += 5
    elif s[i:i+5] == 'erase':
      if s[i+5] == 'r':
        i += 6
      else:
        i += 5
  elif len(s)-i == 6:
    if s[i:i+5] == 'erase':
      if s[i+5] == 'r':
        i += 6
      else:
        i += 5
  elif len(s)-i == 5:
    if s[i:i+5] == 'erase':
      i = len(s)
    elif s[i:i+5] == 'dream':
      i = len(s)
    else:
      i = len(s)+1
if i == len(s):
  print('YES')
else:
  print('NO')

### FIXED CODE ###

s = input()
t = s[::-1]
i = 0
k = len(s)
while i <= k-5:
  if k-i >= 7:
    if t[i] != 'r':
      if t[i:i+5] == 'maerd':
        i += 5
      elif t[i:i+5] == 'esare':
        i += 5
      else:
        i = k+1
    else:
      if t[i:i+6] == 'resare':
        i += 6
      elif t[i:i+7] == 'remaerd':
        i += 7
      else:
        i = k+1
  elif k-i == 6:
    if t[i:i+6] == 'resare':
      i = k
    else:
      i = k+1
  else:
    if t[i:i+5] == 'esare':
      i = k
    elif t[i:i+5] == 'maerd':
      i = k
    else:
      i = k+1
if i == k:
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
H += 2; W += 2
grid = []
grid.append(["#" * W])
for h in range(H-2):
  grid.append(["#" + input() + "#"])
grid.append(["#" * W])

INF = 10**9
ans = 0
for h in range(1, H-1):
  for w in range(1, W-1):
    
    if grid[h][0][w]=="#": continue

    dist = [[INF]*W for i in range(H)]
    dist[h][w] = 0 
    q = deque([(h,w)])

    while(q):
      v_h, v_w = q.popleft()
      d_v = dist[v_h][v_w]
      for n_h, n_w in ((v_h, v_w-1),(v_h, v_w+1),(v_h-1, v_w),(v_h+1, v_w)):
        if grid[n_h][0][n_w]=="#": continue
        d_n = d_v + 1
        if d_n > dist[n_h][n_w]:
          continue
        dist[n_h][n_w] = d_n
        q.append((n_h,n_w))

    new_dist =[]
    for l in dist:
      new_dist.append([x for x in l if x < INF])
    LL = [max(l) if len(l)>0 else 0 for l in new_dist]
    ans = max(ans, max(LL))

print(ans)

      


    


### FIXED CODE ###

from collections import deque
import numpy as np

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

ans = 0
for x in range(H):
    for y in range(W):
        #壁からはスタートできない
        if maze[x][y] == "#":
            continue

        #初期化
        distance = [[0]*W for _ in range(H)]
        #start位置
        stack = deque([[x,y]])

        while stack:
            h,w = stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h, new_w = h+i, w+j
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue
                elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == 0:
                    distance[new_h][new_w] = distance[h][w]+1
                    stack.append([new_h, new_w])

        #start位置は0で初期化
        distance[x][y] = 0
        ans = max(ans, np.max(distance))

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

import numpy as np
N , K ,Q = map(int, input().split())
s = sorted([int(input())-1 for _ in range(Q)])
initializer_list = np.full(N,K,dtype='int')
for i in s:
    tmp = initializer_list[i]
    initializer_list -=1
    initializer_list[i] = tmp
[print('Yes') if i > 0 else print('No')  for i in initializer_list]


### FIXED CODE ###

import numpy as np
N , K ,Q = map(int, input().split())
initializer_list = [0] * N
for _ in range(Q):
    i = int(input())-1
    initializer_list[i] += 1
    

[print('Yes') if (Q - initializer_list[i] < K) else print('No')  for i in range(N)]
### BUGGY CODE ###

import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())

flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        max2step = math.floor(length / 2) # 2段の回数
        count = 1
        for j in range(1,max2step+1) :
            step2 = math.factorial(j)
            step1 = math.factorial(length-2*j)
            count += math.factorial(length - j) // step1 // step2
        ans *= count

    print(int(ans % 1000000007))
else :
    print(0)

### FIXED CODE ###

import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())


flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

fib = [1] * (N+1) # フィボナッチ数列
for i in range(2,N+1) :
    fib[i] = fib[i-1] + fib[i-2]

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        ans *= fib[length]

    print(ans % 1000000007)
else :
    print(0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
n = int(input())
h = list(map(int, input().split()))

max_count = 0
for i in range(n):
    tmp_count = 0
    for j in range(i+1, n):
        if h[j-1] >= h[j]:
            tmp_count += 1
        else:
            break
    if max_count < tmp_count:
        max_count = tmp_count

print(max_count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
n = int(input())
h = list(map(int, input().split()))

max_count = 0
tmp_count = 0
for i in range(n-1):
    if h[i] >= h[i+1]:
        tmp_count += 1
    else:
        if max_count < tmp_count:
            max_count = tmp_count
        tmp_count = 0

if max_count < tmp_count:
    max_count = tmp_count

print(max_count)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [10**10]*n
def dfs(s):
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [None]*n
def dfs(s):
    if dp[s] != None:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])
### BUGGY CODE ###

#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	H, W = getlist()
	A = []
	for i in range(H):
		a = getlist()
		A.append(a)
	B = []
	for i in range(H):
		b = getlist()
		B.append(b)

	for i in range(H):
		for j in range(W):
			A[i][j] -= B[i][j]

	DP = [[[0] * 25601 for i in range(W)] for j in range(H)]
	DP[0][0][A[0][0] + 12800] = 1
	for i in range(H):
		for j in range(W):
			for k in range(25601):
				if DP[i][j][k] == 1:
					if j < W - 1:
						DP[i][j + 1][k + A[i][j + 1]] = 1
						DP[i][j + 1][k - A[i][j + 1]] = 1
					if i < H - 1:
						DP[i + 1][j][k + A[i + 1][j]] = 1
						DP[i + 1][j][k - A[i + 1][j]] = 1

	ans = 1000000
	for i in range(25601):
		if DP[H - 1][W - 1][i] == 1:
			ans = min(ans, abs(12800 - i))
	print(ans)

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

#処理内容
def main():
	H, W = getlist()
	A = []
	for i in range(H):
		a = getlist()
		A.append(a)
	B = []
	for i in range(H):
		b = getlist()
		B.append(b)

	C = [[None] * W for i in range(H)]
	for i in range(H):
		for j in range(W):
			C[i][j] = abs(A[i][j] - B[i][j])

	# print(C)
	diff = 12800
	DP = [[0] * W for i in range(H)]
	DP[0][0] = (1 << (diff + C[0][0])) | (1 << (diff - C[0][0]))
	for i in range(1, W):
		DP[0][i] = (DP[0][i - 1] << C[0][i]) | (DP[0][i - 1] >> C[0][i])
	for i in range(1, H):
		DP[i][0] = (DP[i - 1][0] << C[i][0]) | (DP[i - 1][0] >> C[i][0])

	for i in range(1, H):
		for j in range(W):
			DP[i][j] |= (DP[i][j - 1] << C[i][j]) | (DP[i][j - 1] >> C[i][j])
			DP[i][j] |= (DP[i - 1][j] << C[i][j]) | (DP[i - 1][j] >> C[i][j])

	ans = INF
	for i in range(25601):
		if DP[-1][-1] & (1 << i) == (1 << i):
			ans = min(ans, abs(diff - i))

	print(ans)

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

from collections import Counter
import sys
n=int(input())
s=sys.stdin.readlines()
A=list(map(int,s[0].split()))
C=Counter(A)
        
for i in range(n):
    D=C.copy()
    D[A[i]]-=1
    r=0
    for v in D.values():
        r+=v*(v-1)//2
    print(r)

### FIXED CODE ###

from collections import Counter
import sys
n=int(input())
s=sys.stdin.readlines()
A=list(map(int,s[0].split()))
C=Counter(A)
R=0
for v in C.values():
    R+=v*(v-1)//2
for i in range(n):
    r=C[A[i]]
    X=R
    if r>=2:
        x=((r-1)*(r-2)//2-(r)*(r-1)//2)
        X+=x
    print(X)
### BUGGY CODE ###

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

M = [None] * H
MX = [None] * H
MY = [None] * H

for i in range(H):
  M[i] = [c == '.' for c in input().strip()]
  MX[i] = [None] * W
  MY[i] = [None] * W

max_size = 0

for i in range(H):
  for j in range(W):
    if not M[i][j]: continue

    x_len = 0
    if MX[i][j] is None:
      for x in range(j, W):
        if not M[i][x]: break
        x_len += 1
      for x in range(j, j + x_len):
        MX[i][x] = x_len
    else:
      x_len = MX[i][j]

    y_len = 0
    if MY[i][j] is None:
      for y in range(i, H):
        if not M[y][j]: break
        y_len += 1
      for y in range(i, i + y_len):
        MY[y][j] = y_len
    else:
      y_len = MY[i][j]

    size = x_len + y_len - 1
    max_size = max(max_size, size)

print(max_size)

### FIXED CODE ###

class Counter:
  def __init__(self):
    self.v = 0

  def increment(self):
    self.v += 1


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

M = [None] * H
MX = [None] * H
MY = [None] * H

for i in range(H):
  M[i] = [c == '.' for c in input().strip()]
  MX[i] = [None] * W
  MY[i] = [None] * W

max_size = 0

for i in range(H):
  for j in range(W):
    if not M[i][j]: continue

    if MX[i][j] is None:
      tmp = Counter()
      for x in range(j, W):
        if not M[i][x]: break
        MX[i][x] = tmp
        tmp.increment()

    if MY[i][j] is None:
      tmp = Counter()
      for y in range(i, H):
        if not M[y][j]: break
        MY[y][j] = tmp
        tmp.increment()

    size = MX[i][j].v + MY[i][j].v - 1
    max_size = max(max_size, size)

print(max_size)
### BUGGY CODE ###

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

import re

def nchars(s, n):
    """文字列 s に、同じ文字が n 個以上連続している部分文字列を見つける
    """
    assert n > 0
    reg = re.compile("(.)\\1{%d,}" % (n - 1))  # カンマを取ると n 個ちょうどになる
    while True:
        m = reg.search(s)
        if not m:
            break
        yield m.group(0)
        s = s[m.end():]

s_list = list(nchars(S, 1))
s_list_num = [len(s) for s in s_list]

#print(s_list)
#print(s_list_num)

ans = 0
for i in range(len(s_list)):
    count = 0
    s_len = 0
    for j in range(i, len(s_list)):
        if s_list[j][0] == '0':
            count += 1
            if count > K:
                break
        s_len += s_list_num[j]
        
    ans = max(ans, s_len)

print(ans)
        
        

### FIXED CODE ###

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

import re

def nchars(s, n):
    """文字列 s に、同じ文字が n 個以上連続している部分文字列を見つける
    """
    assert n > 0
    reg = re.compile("(.)\\1{%d,}" % (n - 1))  # カンマを取ると n 個ちょうどになる
    while True:
        m = reg.search(s)
        if not m:
            break
        yield m.group(0)
        s = s[m.end():]

s_list = list(nchars(S, 1))
s_list_num = [len(s) for s in s_list]
if '1' in s_list[0]:
    s_list_num.insert(0,0)
else:
    s_list_num.insert(0,0)
    s_list_num.insert(0,0)


s_list_sum = []
tmp_sum = 0
for x in s_list_num:
    tmp_sum += x
    s_list_sum.append(tmp_sum)

#print(s_list)
#print(s_list_num)
#print(s_list_sum)

ans = 0
for i in range(1, len(s_list_sum),2):

    l_sum = s_list_sum[i-1]
    r_sum = s_list_sum[min(len(s_list_sum)-1, i+K*2)]
    #print(l_sum, r_sum)
    ans = max(ans, r_sum - l_sum)

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

def main():
    S = input()
    S = S[::-1]

    dp = [[0] * 15 for _ in range(len(S) + 5)]
    MOD = 10**9 + 7

    dp[0][0] = 1

    for i in range(len(S)):
        for j in range(13):
            if S[i] != '?':
                k = int(S[i])
                dp[i+1][(j+k*10**i)%13] += dp[i][j]
                dp[i+1][(j+k*10**i)%13] %= MOD
            else:
                for k in range(10):
                    dp[i+1][(j+k*10**i)%13] += dp[i][j]
                    dp[i+1][(j+k*10**i)%13] %= MOD


    print(dp[len(S)][5])



main()

### FIXED CODE ###

def main():
    S = list(input())

    dp = [0] * 13
    dp[0] = 1
    mod = 10**9 + 7
    digit = 1
    for i in range(len(S)-1,-1,-1):
        nextdp = [0] * 13
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    nextdp[(j * digit + k) % 13] += dp[k]
                    # あらかじめ10*9 + 7で割って余りを出しておく
                    nextdp[(j * digit + k) % 13] %= mod
        else:
            j = int(S[i])
            for k in range(13):
                nextdp[(j * digit + k) % 13] += dp[k]
                # あらかじめ10*9 + 7で割って余りを出しておく
                nextdp[(j * digit + k) % 13] %= mod
        
        digit *= 10
        # A * 桁数の13で割ったあまりは (A % 13) * (桁数 % 13)のため、桁数を13で割っておく
        digit %= 13
        dp = nextdp
    
    print(dp[5])

main()
### BUGGY CODE ###

from collections import deque,defaultdict

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

g=defaultdict(list)
for _ in range(N-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)

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

visited=[False]*(N+1)
q=deque([])
q.append([1,0])
res=[0 for i in range(N+1)]
while q:
    i,c = q.pop()
    if visited[i]:
        continue
    visited[i]=True
    ch=g[i]
    w=c+f[i]
    res[i]=w
    for u in ch:
        q.appendleft([u,w])

print(*res[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N,Q,*abpx=map(int,sys.stdin.read().split())

graph=[[] for _ in range(N)]
for a,b in zip(*[iter(abpx[:2*(N-1)])]*2):
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)

f=[0]*N
for p,x in zip(*[iter(abpx[2*(N-1):])]*2):
    p-=1
    f[p]+=x

ans=[0 for _ in range(N)]
visited=[False]*N
def c(i,p):
    if visited[i]:
        return 
    visited[i]=True
    w=f[i]+p
    ans[i]=w
    ch=graph[i]
    for x in ch:
        c(x,w)

c(0,0)
print(*ans)
### BUGGY CODE ###

h,w=map(int,input().split())
a_list=[]
for i in range(h):
    b=list(input())
    a_list.append(b)
count=-1
end=0
while end==0:
    end=1
    c_list=[]
    for i in range(h):
        for j in range(w):
            if a_list[i][j]=='#':
                if i>0:
                    c_list.append((i-1,j))
                if i<h-1:
                    c_list.append((i+1,j))
                if j>0:
                    c_list.append((i,j-1))
                if j<w-1:
                    c_list.append((i,j+1))
            else:
                end=0
    for k in c_list:
        a_list[k[0]][k[1]]='#'
    count=count+1
print(count)


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
INF=10**9
check=[]
for i in range(h):
    sub_list=[]
    for j in range(w):
        sub_list.append(INF)
    check.append(sub_list)
black=deque([])
for i in range(h):
    sub_list=list(input())
    for j in range(w):
        if sub_list[j]=='#':
            black.append((i,j))
            check[i][j]=0
Max=0
while len(black)>0:
    now=black.popleft()
    U=(now[0]-1,now[1])
    D=(now[0]+1,now[1])
    L=(now[0],now[1]-1)
    R=(now[0],now[1]+1)
    for i in U,D,L,R:
        if 0<=i[0]<=h-1 and 0<=i[1]<=w-1 and check[i[0]][i[1]]==INF:
            check[i[0]][i[1]]=check[now[0]][now[1]]+1
            Max=max(Max,check[i[0]][i[1]])
            black.append(i)
print(Max)
### BUGGY CODE ###

n, t = map(int, input().split())
ab = sorted(list(map(int, input().split())) for _ in range(n))
dp = [-1] * (t - 1) + [0]
ret = 0
for i in range(n):
    a, b = ab[i]
    newdp = dp[:]
    for j in range(t):
        if dp[j] >= 0:
            ret = max(ret, dp[j] + b)
            if j - a >= 0:
                newdp[j - a] = max(newdp[j - a], dp[j] + b)
    dp = newdp
print(ret)


### FIXED CODE ###

n, t = map(int, input().split())
ab = sorted(list(map(int, input().split())) for _ in range(n))
dp = [-1] * (t - 1) + [0]
ret = 0
for i in range(n):
    a, b = ab[i]
    newdp = dp[:]
    for j in range(t):
        if dp[j] >= 0:
            ret = max(ret, dp[j] + b)
            if j - a >= 0:
                newdp[j - a] = max(newdp[j - a], dp[j] + b)
    dp = newdp
print(ret)
### BUGGY CODE ###

import bisect

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

alist = sorted(list(map(int, input().split())))

for _ in range(m):
  b, c = map(int, input().split())
  idx = bisect.bisect_right(alist,c)
  if idx-1 <= b:
    alist = [c for _ in range(idx)] + alist[idx:]
  else:
    idx2 = idx-b
    alist = alist[b:idx2+b] + [c for _ in range(b)] + alist[b+idx2:]  
print(sum(alist))

### FIXED CODE ###

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

CB = []
for _ in range(M):
  b,c = map(int,input().split())
  CB.append([c,b])
CB.sort(reverse=True)

num = 0
ans = 0 
for c,b in CB:
  for bi in range(b):
    if num >= N: break
    if num > N or c<=A[num]:
      break
    else:
      num += 1
      ans += c
print(ans+sum(A[num:]) if num != N else ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())

in_p = []
in_y = []
p = []

for _ in range(n):
    p.append([])

for i in range(m):
    a,b = map(int,input().split())
    in_p.append(a)
    in_y.append(b)
    p[a-1].append(b)  

for i in range(n):
    p[i].sort()

for i in range(m):
    year=str(in_p[i]).zfill(6)
    a = p[in_p[i]-1].index(in_y[i]) + 1
    num=str(a).zfill(6)
    print("{0}{1}".format(year,num))



### FIXED CODE ###

import copy

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

cnt = [0]*(10**5+4)

yy = []
yp = []
for _ in range(m):
    a,b = map(int,input().split())
    a,b = b,a
    yy.append([a,0])
    yp.append([a,b])

inlist = copy.deepcopy(yp)
yp.sort()
yy = dict(yy)

for i in range(m):
    cnt[yp[i][1]]+=1
    yy[yp[i][0]] = cnt[yp[i][1]]

for key,value in inlist:
    print("{:06}{:06}".format(value,yy[key]))
### BUGGY CODE ###

def resolve():
    n, m = map(int, input().split())
    li_broken = [int(input()) for _ in range(m)]
    dp = [0] * (n + 2)
    
    dp[n] = 1

    for i in reversed(range(n)):

        if i in li_broken:
            dp[i] = 0
            continue

        dp[i] = (dp[i+1] + dp[i+2]) % 1000000007

    print(dp[0])
    
resolve()

### FIXED CODE ###

def step(n):
  if n == 0:
      return 1
  steps = [0 for i in range(n + 2)]
  steps[1] = 1
  steps[2] = 2
  for i in range(3, n + 1):
    steps[i] = steps[i - 1] + steps[i - 2]
  return steps[n]

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

a.append(n)

sum = 1

for i in range(m + 1):

  if i == 0:
    sum *= step(a[i] - 1)
    continue
  
  elif i == m:
    sum *= step(a[m] - a[m-1] -1)
    
  elif a[i] - a[i-1] == 1:
    sum = 0
    break

  else:
    sum *= step(a[i] - a[i-1] -2)
    
if m == 0:
  sum = step(n)

print(sum % 1000000007)