Harryxun/stf_run huggingface dataset:
import math
N = int(input())
P = list(tuple(map(int, input().split())) for _ in range(N))

M = 0
for i in range(N):
    for j in range(1,N):

        M = max(M, math.sqrt((P[i][0]-P[j][0]) ** 2 + (P[i][1]-P[j][1]) ** 2))

print("{:.6f}".format(M))

### FIXED CODE ###

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

cnt = 0

if S <= 0:
  cnt += 1
else:

  if K >= S:
      cnt+=3

  def cnt2(k, s):
      if 2 * k >= s:
          if s - 1 <= k:
              return s-1
          else:
              return k-(s-k)+1
      else:
          return 0

  cnt+=3*cnt2(K, S)

  for x in range(1, K+1):
      if S-x <=0:
          break
      cnt += cnt2(K, S-x)

print(cnt)
N,A,B = map(int,input().split())
output = 0
for i in range(1,N+1): 
  # set condition for i < 10^4
  if i < 10:
	digitsum = i
  elif i<100:
    digitsum = i//10+i%10
  elif i<1000:
    digitsum = i//100+(i%100)//10+(i%100)%10
  elif i<10000:
    digitsum= i//1000+(i%1000)//100+((i%1000)%100)//10+((i%1000)%100)%10
  else:
    digitsum = 0
 
  if A <= digitsum and digitsum <= B:
  	output += i
    
print (output)
N,A,B = map(int,input().split())
output = 0
for i in range(1,N+1): 
  # set condition for i < 10^4
  if i < 10:
	digitsum = i
  elif i<100:
    digitsum = i//10+i%10
  elif i<1000:
    digitsum = i//100+(i%100)//10+(i%100)%10
  elif i<10000:
    digitsum= i//1000+(i%1000)//100+((i%1000)%100)//10+((i%1000)%100)%10
  else:
    digitsum = 1
 
  if A <= digitsum and digitsum <= B:
  	output += i
    
print (output)


### FIXED CODE ###

 
N,A,B=map(int,input().split())
 
sum_k=0
 
for i in range(N+1):
    if i <10:
        k=i
    elif i<100:
        k=i//10+i%10
    elif i<1000:
        k=i//100+(i%100)//10+(i%100)%10
    elif i<10000:
        k=i//1000+(i%1000)//100+((i%1000)%100)//10+((i%1000)%100)%10
    else:
        k=1
    if A<=k and k<=B:
        sum_k=sum_k+i
      
print(sum_k)
x = input()
print(int(x**3))

### FIXED CODE ###

x = input()
i = int(x)
print(i**3)
n = int(input())
s = str(n)
x = 0

for i in s:
    x += int(i)
print(x)
if n % x == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = str(input())
ans = s.count("+") - s.count("-")

print(ans)
import collections
N = map(int, input().split())
A = list(map(int, input().split()))
Q = map(int, input().split())
 
base = 0
cnt = collections.Counter(A)    
Ans = []
 
for i in range(N):
    base += A[i]

for i in range(Q):
  b ,c = map(int, input().split())
  Ans.append(base + (c-b) * cnt[b])
  cnt[c] += cnt[b]
  cnt[b] = 0
  base = Ans[i]

print(Ans)

### FIXED CODE ###

import collections

n = int(input())
A = list(map(int, input().split()))
q = int(input())

CNT = collections.Counter(A)
ANS = []
ans = sum(A)

for i in range(q):
    b, c = map(int, input().split())
    t = CNT[b]
    ans +=(c - b) * t
    ANS.append(ans)
    CNT[c] += t
    CNT[b] = 0

for i in ANS:
    print(i)
N, M = map(int, input().split())
data = {}
canMake = True
for _ in range(M):
  s, c = map(int, input().split())
  if s in data:
    if data[s] != c:
      canMake = False
  else:
    data[s] = c

keta = max(data)
pad = min(data)
if data[min(data)] == 0:
  canMake = False

if not canMake:
  print(-1)
  exit()

res = 0
for i in range(1, keta+1):
  if i in data:
    res += data[i]*10**(keta-i)
  elif i < pad:
    res += 10**(keta-i)

print(res)

### FIXED CODE ###

N, M = map(int, input().split())
data = {}
canMake = True
if M == 0:
  if N == 1:
    print(0)
  if N == 2:
    print(10)
  if N == 3:
    print(100)
  exit()

for _ in range(M):
  s, c = map(int, input().split())
  if s in data:
    if data[s] != c:
      canMake = False
  else:
    data[s] = c

keta = N
pad = min(data)
if N != 1 and min(data) == 1 and data[min(data)] == 0:
  canMake = False

if not canMake:
  print(-1)
  exit()

res = 0
for i in range(1, keta+1):
  if i in data:
    res += data[i]*10**(keta-i)
  elif i == 1:
    res += 10**(keta-i)

print(res)
sum = 0
for i in range(3)
	tmp = input().split()
	sum += int(tmp[0])+int(tmp[1])int(tmp[2])
if sum%3 ==0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

sum = 0
list = [[0 for x in range(3)] for y in range(3)]
for i in range(3):
    tmp = input().split()
    list[i] = tmp
    sum += int(tmp[0]) + int(tmp[1]) + int(tmp[2])

flg = True
if sum%3 ==0:
    for n in range(2):
        for m in range(2):
            if (int(list[n][m]) + int(list[n+1][m+1]))!=(int(list[n+1][m])+int(list[n][m+1])):
                flg = False
                break
    if flg:
        print('Yes')
    else:
        print('No')
else:
  print('No')
X = int(input())
if x => 30:
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

x = int(input())
if x >= 30:
  print("Yes")
else:
  print("No")
import fractions as math
a,b,x=map(int,input().split())
if a*a*b/2<x:
    theta=a/(2*b-2*x/a**2)
else:
    theta=2*x/(a*b*b)
print(90-math.atan(theta)*180/math.pi)

### FIXED CODE ###

import math
a,b,x=map(int,input().split())
if a*a*b/2<x:
    theta=(2*b-2*x/a**2)/a
else:
    theta=b**2*a/2/x
print(math.atan(theta)*180/math.pi)
N = int(input())
A = list(map(int,input().split()))
Sum = 0

for i in range(N-1):
  if(A[N] - A[N+1] > 0):    
    Sum += A[N] - A[N+1]
    A[N+1] += A[N] - A[N+1]
    
print(Sum)

### FIXED CODE ###

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

for i in range(N-1):
  if(A[i] - A[i+1] > 0):
    Sum += A[i] - A[i+1]
    A[i+1] += A[i] - A[i+1]
 
print(Sum)
def main():
	n,m,q = map(int,input().split())
	qu = [list(map(int,input().split())) for x in range(q)]
	ans = 0
	import itertools

	alist = list(itertools.product([1,2,3,4,5,6,7,8,9,10],repeat = m))
	ans_list = set()
	for i in alist:
		for qul in range(q):
			if i[ qu[qul][1]-1 ] - i[ qu[qul][0]-1 ] == qu[qul][2] and list(i) == sorted(i):
				ans += qu[qul][3]
		ans_list.add(ans)
		ans = 0
	print(max(ans_list))

if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	n,m,q = map(int,input().split())
	qu = [list(map(int,input().split())) for x in range(q)]
	ans = 0
	import itertools

	ans_list = set()
	for i in itertools.combinations_with_replacement(list(range(1,m+1)),n):
		for qul in range(q):
			if i[ qu[qul][1]-1 ] - i[ qu[qul][0]-1 ] == qu[qul][2]:
				ans += qu[qul][3]
		ans_list.add(ans)
		ans = 0
	print(max(ans_list))

if __name__ == '__main__':
	main()
n = int(input())
a = list(map(int, input().split()))
s = []
m = 1

def f(m, a):
    s_tmp = 0
    for i in range(n):
        s_tmp = s_tmp + m % a[i]
    return s_tmp

for i in range(n):
    m = m * a[i]

print(f(m-1, a))

### FIXED CODE ###

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

a.sort()

print(a[2]- a[0])
from fractions import gcd

INF = 2 << 30
V = 1003
G = [[] for _ in xrange(V)]
visited = [False]*V

def add_edge(fro, to, cap):
    G[fro].append([to,cap,len(G[to])])
    G[to].append([fro,0,len(G[fro])-1])

def dfs(v,t,f):
    if v == t:
        return f
    visited[v] = True
    for i,(to,cap,rev) in enumerate((G[v])):
        if visited[to] or cap <= 0:            
            continue        
        d = dfs(to,t,min(f,cap))
        if d > 0:
            G[v][i][1] -= d
            G[to][rev][1] += d
            return d
    return 0

def max_flow(s,t):
    flow = 0
    while True:
        for i in xrange(V):
            visited[i] = False
        f = dfs(s,t,INF)
        if f == 0:
            return flow
        flow += f

while True:
    m,n = map(int,raw_input().split())
    if m|n == 0:
        break
    V = m+n+2
    G = [[] for _ in xrange(V)]
    data = []
    while len(data) < n+m:
        data += map(int,raw_input().split())            
    blue = data[:m]
    red = data[m:]
    for i,b in enumerate(blue):
        add_edge(V-2,i,1)
    for i,r in enumerate(red):
        add_edge(i+m,V-1,1)
    for i in xrange(m):
        for j in xrange(n):
            if gcd(blue[i],red[j]) != 1:
                add_edge(i,j+m,1)
    print max_flow(V-2,V-1)

### FIXED CODE ###

from fractions import gcd

V = 1001
G = []
visited = []
match = []

def add_edge(u,v):
    G[u].append(v)
    G[v].append(u)

def dfs(v):
    visited[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not visited[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True

def bipartite_matching():
    global match,visited
    res = 0
    match = [-1]*V
    for v in xrange(V):
        if match[v] < 0:
            visited = [False]*V
            if dfs(v):
                res += 1
    return res

while True:
    m,n = map(int,raw_input().split())
    V = m+n
    if V == 0:
        break
    G = [[] for _ in xrange(V)]
    data = []
    while len(data) < V:
        data += map(int,raw_input().split())
    for i,b in enumerate(data[:m]):
        for j,r in enumerate(data[m:],m):
            if gcd(b,r) != 1:
                add_edge(i,j)
    print bipartite_matching()
import math
n, k = map(int, input().split())

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1, k+1):
    c = 1
    c *= comb(n-k+1, i)
    c *= comb(k-1, i-1)
    print(c%(10**9+7))

### FIXED CODE ###

import math
n, k = map(int, input().split())
 
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
 
for i in range(1, k+1):
    if i <= n - k + 1:
        c = 1
        c *= comb(n-k+1, i)
        c *= comb(k-1, i-1)
        print(c%(10**9+7))
    else:
        print(0)
t = input().split()
n = int(t[0])
m = int(t[1])

low = 0
high = n
for i in range(0, m):
  tmp = input().split()
  if int(tmp[0]) > low:
    low = int(tmp[0])
  if int(tmp[1]) < high:
    high = int(tmp[1])

if high =< low:
  num = 0
else:
  num = high-low+1
print(num)

### FIXED CODE ###

t = input().split()
n = int(t[0])
m = int(t[1])

low = 0
high = n
for i in range(0, m):
  tmp = input().split()
  if int(tmp[0]) > low:
    low = int(tmp[0])
  if int(tmp[1]) < high:
    high = int(tmp[1])

if (high-low)<0:
  num = 0
else:
  num = high-low+1
print(num)
from sys import stdin
input = stdin.readline

L, N = map(int, input().split())
D = []

for i in range(N):
    D.append(input()

D.sort()

print(''.join(D))

### FIXED CODE ###

from sys import stdin
input = stdin.readline

N, L = map(int, input().split())
D = []

for i in range(N):
    D.append(input().strip())
D.sort()
print(''.join(D))
a, b, c = map(int, input().split())
list = []
list.append( max(a,b)-min(a,b) )
list.append( max(b,c)-min(b,c) )
list.append( max(a,c)-min(a,c) )

mini = list.pop(min(list))
ans = mini + min(list)

print(ans)

### FIXED CODE ###

a = list(map(int, input().split()))
a.sort()
#print(a)
ans = (a[2]-a[1])+(a[1]-a[0])
print(ans)
#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

Q, H, S, D, N = map(int, read().split())

dp = [1<<60] * (N + 2)

dp[0] = 0

for i in range(1, N+1):
    dp[i] = min([dp[i-1] + Q * 4, dp[i-1] + Q*2 + H, dp[i-1] + H*2, dp[i-1] + S])
    if i >= 2:
        dp[i] = min(dp[i], dp[i-2] + D)

print(dp[N])


### FIXED CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

Q, H, S, D, N = map(int, read().split())
H = min(Q * 2, H)
S = min(H *2 , S)

if S * 2 < D:
    print(N * S)
else:
    print(N // 2 * D + N % 2 * S)
s=input()
if s[-1]=='s':
  	s+='es'
  	return s
s+='s'
return s


### FIXED CODE ###

s=str(input())
if(s[-1]=="s"):
  	print(s+"es")
else:
	print(s+"s")
n, m = map(int, input().split())
a = [[None] * m for _ in range(n)]
b = [None] * m
for i in range(n):
    a[i] = list(map(int, input().split()))
for i in range(m):
    b[i] = int(input())
for _ in range(n):
    c = None
    for i in range(m):
        c += a[i] * b[i]
    print(c)



### FIXED CODE ###

n, m = map(int, input().split())
A = [map(int, input().split()) for _ in [None] * n]
b = [int(input()) for _ in [None] * m]
for a in A:
    print(sum(i * j for i, j in zip(a, b)))
h,w,d = map(int,input().split())
p = [(0,0)] * (h*w)
c = [0] * (h*w)
for i in range(h):
  a = list(map(int,input().split()))
  for j in range(w):
    p[a[j]-1] = (i,j)

for i in range(d, h*w):
  c[i] = c[i-d] + abs(p[i][0] - p[i-d][0]) + abs(p[i][1] - p[i-d][1])

q = int(input())
ans = 0
for i in range(q):
  l,r = map(int,input().split())
  ans += c[r] - c[l]
print(ans)

### FIXED CODE ###

h,w,d = map(int,input().split())
p = [(0,0)] * (h*w)
c = [0] * (h*w)
for i in range(h):
  a = list(map(int,input().split()))
  for j in range(w):
    p[a[j]-1] = (i,j)

for i in range(d, h*w):
  c[i] = c[i-d] + abs(p[i][0] - p[i-d][0]) + abs(p[i][1] - p[i-d][1])

q = int(input())
ans = 0
for i in range(q):
  l,r = map(int,input().split())
  print(c[r-1] - c[l-1])
N=int(input())
res=0
for n in N:
  l,r=[int(x) for x in input().split()]
  res+=r-l+1
else:
  print(res)

### FIXED CODE ###

N=int(input())
res=0
for n in range(N):
  l,r=[int(x) for x in input().split()]
  res+=r-l+1
else:
  print(res)
n, x = map(int,input().split())

def rec(lv,ls):
    if lv == 0:
        return [1]
    else:
        ret = rec(lv-1,ls)
        for i in range(0,len(ret) -1):
            if ret[i]>0 and ret[i+1]>0:
                ret[i+1] += ret[i]
                ret[i] = 0  #deleted tag

        while 0 != ret.count(0):
            ret.remove(0)
        return [-1,*ret,1,*ret,-1]

 
count = 0
for e in rec(n, list() ):
    abs_e = abs(e)
    if x>=abs_e:
        x -= abs_e
        count += e if e>0 else 0
    else:
        count += e if e>0 else 0


print(count)


### FIXED CODE ###


# This src was written after reading editional.pdf .

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


an, pn = [1], [1]

for i in range(n):
    an.append(2*an[i]+3)
    pn.append(2*pn[i]+1)

#print(an)

def f(n,x):

    #print(n,x)

    if n == 0:
        return 1 if 0<x else 0
    
    if x <= an[ n-1 ] + 1:
        return f( n-1, x-1 )

    else:# x <= 2*an[n-1] + 3:
        return f(n-1, x-an[n-1]-2) + pn[n-1] + 1


print(f(n,x))

    
#    else if: 
#        pass
n = int(input())
l = list(map(int,input().split()))
ans = 0
for i in range(n):
  if l[i]>l[i+1]:
    ans = ans + l[i]-l[i+1]
    l[i+1] = l[i]

print(ans)
  

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
m = []
for i in range(n-1):
  if l[i]>l[i+1]:
     m.append(l[i]-l[i+1])
     l[i+1] = l[i]

print(sum(m))
input_str = input()
homes = input_str.split(" ")
for home in homes:
    home = int(home)
print(homes)
if ((homes[2] - homes[1]) * (homes[2] - homes[0]) < 0):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

input_str = input()
homes = input_str.split(" ")
for i, home in enumerate(homes):
    homes[i] = int(home)
if ((homes[2] - homes[1]) * (homes[2] - homes[0]) < 0):
    print("Yes")
else:
    print("No")
t1 = [int(i) for i in input().split()]
total = list1[0]*500
 
if total > list1[1]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

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

total = k * 500
if total >= x:
  print("Yes")
else:
  print("No")
import sys
readline=sys.stdin.readline

import numpy as np
from numba import njit,i8

N,K=map(int,readline().split())
DIV = 998244353
steps = []
for i in range(K):
  l,r = map(int,readline().split())
  for j in range(l, r + 1):
    steps.append(j)
    
steps = sorted(steps)
steps = np.array(steps, dtype = int)

@njit(i8(i8[:]),cache = True)
def solve(steps):
  dp = np.zeros(N, dtype = int)
  dp[0] = 1
  for i in range(len(dp)):
    for s in steps:
      if i + s >= len(dp):
        break
      dp[i + s] += dp[i]
      dp[i + s] %= DIV
      
  return dp[-1]

print(solve())


### FIXED CODE ###

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
DIV = 998244353

L = [None] * K
R = [None] * K
for i in range(K):
  L[i],R[i] = map(int,readline().split())

dp = [0] * (N + 1)
sdp = [0] * (N + 1)
dp[1] = 1
sdp[1] = 1
  
for i in range(2, len(dp)):
  for j in range(K):
    li = max(i - R[j], 0)
    ri = i - L[j]
    if ri < 0:
      continue
    dp[i] += (sdp[ri] - sdp[li - 1])
    dp[i] %= DIV
  sdp[i] = sdp[i - 1] + dp[i]
  sdp[i] %= DIV
  
print(dp[N])
ans=o
n,k=map(int,input().split())
while n!=0:
  n=n//k
  ans+=1
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
ans=0
while n!=0:
  n=n//k
  ans+=1
print(ans)
import sys
from collections import deque
l,n=map(int,input().split())
p=n//2
q=(n+1)//2
r=(n-1)//2
tree1=[int(i) for i in sys.stdin]
reversed_tree1=[l-i for i in reversed(tree1)]
tree=deque(tree1)
reversed_tree=deque(reversed_tree1)
if n%2 == 0:
  ans= sum(tree1)*2 + l*(n-1) +tree1[p] - sum(tree1[p:])*4
  ans2= sum(reversed_tree1)*2 + l*(n-1) +reversed_tree1[p] - sum(reversed_tree1[p:])*4
  p-=1
  ans3= ans-tree.popleft()*2-l+tree[p]*2
  ans= max(ans,ans3)
  ans4= ans2-reversed_tree.popleft()*2-l+(reversed_tree[p])*2
  ans2= max(ans2,ans4)
else:
  ans= sum(tree1)*2 + l*(n-1) - tree1[p] - sum(tree1[q:])*4
  ans3=ans
  ans2= sum(reversed_tree1)*2 + l*(n-1) - reversed_tree1[p] - sum(reversed_tree1[q:])*4
  ans4=ans2
while len(tree)>1:
  q-=1
  r-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[r]+tree[q]
  ans= max(ans_stack,ans)
  ans3=ans_stack
  p-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[p]*2
  ans=max(ans_stack,ans)
  ans3=ans_stack
p=n//2
q=(n+1)//2
r=(n-1)//2
while len(reversed_tree)>1:
  q-=1
  r-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[r]+reversed_tree[q]
  ans2=max(ans_stack,ans2)
  ans4=ans_stack
  p-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[p]*2
  ans2=max(ans2,ans_stack)
  ans4=ans_stack
print(max(ans,ans2))


### FIXED CODE ###

import sys
from collections import deque
l,n=map(int,input().split())
c=n
tree1=[int(i) for i in sys.stdin]
reversed_tree1=[l-i for i in reversed(tree1)]
tree=deque(tree1)
reversed_tree=deque(reversed_tree1)
if n%2 == 0:
  ans= sum(tree1)*2 + l*(n-1) +tree1[n//2] - sum(tree1[n//2:])*4
  ans2= sum(reversed_tree1)*2 + l*(n-1) +reversed_tree1[n//2] - sum(reversed_tree1[n//2:])*4
  n-=1
  c-=1
  ans3= ans-tree.popleft()*2-l+tree[n//2]*2
  ans= max(ans,ans3)
  ans4= ans2-reversed_tree.popleft()*2-l+(reversed_tree[n//2])*2
  ans2= max(ans2,ans4)
else:
  ans= sum(tree1)*2 + l*(n-1) - tree1[n//2] - sum(tree1[((n//2)+1):])*4
  ans3=ans
  ans2= sum(reversed_tree1)*2 + l*(n-1) - reversed_tree1[n//2] - sum(reversed_tree1[((n//2)+1):])*4
  ans4=ans2
for i in range(n//2):
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[(n-1)//2]+tree[(n+1)//2]
  ans= max(ans_stack,ans)
  ans3=ans_stack
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[n//2]*2
  ans=max(ans_stack,ans)
  ans3=ans_stack
n=c
for i in range(n//2):
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[(n-1)//2]+reversed_tree[(n+1)//2]
  ans2=max(ans_stack,ans2)
  ans4=ans_stack
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[n//2]*2
  ans2=max(ans2,ans_stack)
  ans4=ans_stack
print(max(ans,ans2))
a,b,k=map(int,input().split())
A=a
B=b
if a>=k:
    A=a-k
elif a<k:
    B=b-(k-a)
    A=0
    if B<0
       　B=0
else:
    A=0
    B=0
    
print(A,B)

### FIXED CODE ###

a,b,k=map(int,input().split())
#食べられた後のa
A=a
#食べられた後のb
B=b
K=k

if a>=k:
    A=a-k
    print(A,B)
elif a<k:
    B=b-(k-a)
    A=0
    if k-a>=b:
        B=0
    print(A,B)
else:
    A=0
    B=0
    print(A,B)
from collections import deque

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

tmp = [0 for _ in range(N + 1)]

now = 0

if 1 not in A:
    tmp[1] = 1
    
else:
    now += 1
    
if N >= 2:
    if 2 not in A:
        tmp[2] = tmp[1] + 1
    
    else:
        now += 1

if now >= M:
    now = 0

for i in range(3, N+1):
    
    if i != A[now]:
        tmp[i] = tmp[i-1] + tmp[i-2] 
        
    else:
        if now < M - 1:
            now += 1
        

    
print(tmp[-1]%(10**9+7))




### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

tmp = [0 for _ in range(N + 1)]

now = 0
if 1 not in A:
    tmp[1] = 1
    
else:
    now += 1
    
if (2 not in A) and N >= 2:
    tmp[2] = tmp[1] + 1
    
else:
    now += 1

for i in range(3, N+1):
    
    try:
        if i != A[now]:
            tmp[i] = tmp[i-1] + tmp[i-2] 
            
        else:
            now += 1
        
    except:
        tmp[i] = tmp[i-1] + tmp[i-2] 

    
print(tmp[-1]%(10**9+7))
S = input()
x, y = map(int, input().split())

a = []
t = 0
for s in S:
    if s == "F":
        t += 1
    else:
        a.append(t)
        t = 0
a.append(t)

if a == []:
    if x == y == 0:
        print("Yes")
        exit(0)
    else:
        print("No")
        exit(0)

d = [[a[0],0]]
for k in range(1,len(a)):
    n = []
    if k%2 == 1:
        for e in d:
            n.append([e[0],e[1]+a[k]])
            n.append([e[0],e[1]-a[k]])
    else:
        for e in d:
            n.append([e[0]+a[k],e[1]])
            n.append([e[0]-a[k],e[1]])
    d = list(set(n))

print("Yes" if [x,y] in d else "No")


### FIXED CODE ###

S = input()
x, y = map(int, input().split())

a = []
t = 0
for s in S:
    if s == "F":
        t += 1
    else:
        a.append(t)
        t = 0
a.append(t)

if a == []:
    if x == y == 0:
        print("Yes")
        exit(0)
    else:
        print("No")
        exit(0)

X = [a[0]]
Y = [0]

for k in range(1,len(a)):
    if k%2 == 0:
        nx = []
        for e in X:
            nx.append(e+a[k])
            nx.append(e-a[k])
        X = list(set(nx))
    else:
        ny = []
        for e in Y:
            ny.append(e+a[k])
            ny.append(e-a[k])
        Y = list(set(ny))

print("Yes" if x in X and y in Y else "No")
import sys
input = sys.stdin.readline

import numpy as np

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = np.zeros((N+1,W+1), dtype=np.int64)
    #dp = [[0]*(W+1) for i in range(N+1)]

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

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if wv[i-1][0] <= j: #dpの横が重さだが，jが重さ以下ならそもそも入れられない．
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
            #print(i,j)
            #print(*dp,sep="\n")

    #4:出力
    print(dp[N][W])

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()