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

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

a = []
for i in range(H):
    a.append(str(input()))

R = [[0] * W for i in range(H)]
L = [[0] * W for i in range(H)]
D = [[0] * W for i in range(H)]
U = [[0] * W for i in range(H)]

for i in range(H):
    cur = 0
    for j in range(W):
        if a[i][j] == "#":
            cur = 0
            U[i][j] = 0
        else:
            cur += 1
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] += U[i-1][j] + 1
        L[i][j] = cur

for i in reversed(range(H)):
    cur = 0
    for j in reversed(range(W)):
        if a[i][j] == "#":
            cur = 0
            D[i][j] = 0
        else:
            cur += 1
            if i == (H-1):
                D[i][j] = 1
            else:
                D[i][j] += D[i+1][j] + 1
        R[i][j] = cur

ans = 0
for i in range(H):
    for j in range(W):
        if L[i][j] + R[i][j] + D[i][j] + U[i][j] -3 > ans:
            ans = L[i][j] + R[i][j] + D[i][j] + U[i][j] -3

print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

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

a = []
for i in range(H):
    a.append(str(input()))

R = [[0] * W for i in range(H)]
L = [[0] * W for i in range(H)]
D = [[0] * W for i in range(H)]
U = [[0] * W for i in range(H)]

for i in range(H):
    cur = 0
    for j in range(W):
        if a[i][j] == "#":
            cur = 0
            U[i][j] = 0
        else:
            cur += 1
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] += U[i-1][j] + 1
        L[i][j] = cur

ans = 0
for i in reversed(range(H)):
    cur = 0
    for j in reversed(range(W)):
        if a[i][j] == "#":
            cur = 0
            D[i][j] = 0
        else:
            cur += 1
            if i == (H-1):
                D[i][j] = 1
            else:
                D[i][j] += D[i+1][j] + 1
        R[i][j] = cur
        if L[i][j] + R[i][j] + D[i][j] + U[i][j] -3 > ans:
            ans = L[i][j] + R[i][j] + D[i][j] + U[i][j] -3

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

import sys
#input = sys.stdin.readline

def main():
    h,w=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    flg=['#','.']
    def dfs(x,y,f):
        a,b=0,0
        if x<h-1:
            if s[x+1][y]==flg[f]:
                a=dfs(x+1,y,f)
            else:
                a=dfs(x+1,y,(f+1)%2)+1
        if y<w-1:
            if s[x][y+1]==flg[f]:
                b=dfs(x,y+1,f)
            else:
                b=dfs(x,y+1,(f+1)%2)+1
        return min(a,b)

    if s[0][0]=='#':
        print(dfs(0,0,0)+1)
    else:
        print(dfs(0,0,1))
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
#input = sys.stdin.readline

def main():
    h,w=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    ans=[[0]*w for _ in range(h)]
    if s[0][0]=='#':
        ans[0][0]=1
    for i in range(h):
        for j in range(w):
            if i==0:
                if j==0:
                    continue
                else:
                    if s[i][j]==s[i][j-1]:
                        ans[i][j]=ans[i][j-1]
                    else:
                        ans[i][j]=ans[i][j-1]+1
            else:
                if j==0:
                    if s[i][j]==s[i-1][j]:
                        ans[i][j]=ans[i-1][j]
                    else:
                        ans[i][j]=ans[i-1][j]+1
                else:
                    if s[i][j]==s[i][j-1]:
                        a=ans[i][j-1]
                    else:
                        a=ans[i][j-1]+1
                    if s[i][j]==s[i-1][j]:
                        b=ans[i-1][j]
                    else:
                        b=ans[i-1][j]+1
                    ans[i][j]=min(a,b)
    A=ans[h-1][w-1]
    if A%2==1:
        print(A//2+1)
    else:
        print(A//2)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import heapq

INF = float('inf')


class PriorityQueue:
    def __init__(self):
        self.__queue = []
        self.__count = 0

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__queue, v)

    def dequeue(self):
        self.__count -= 1
        return heapq.heappop(self.__queue)

    def is_empty(self)->bool:
        return self.__count == 0


def dijkstra(V: int, E: list, s: int, t: int)->int:
    '''dijkstra 法を使って u -> v の距離を求める。
    :param V: 頂点数
    :param E: 辺の集合
    :param s: 始点
    :param t: 終点
    :return: 距離
    '''
    d = [INF] * (V)
    d[s] = 0

    q = PriorityQueue()
    for v in range(V):
        q.enqueue((d[v], v))

    while not q.is_empty():
        _, u = q.dequeue()
        for v, c in E[u]:
            if d[u] + c < d[v]:
                d[v] = d[u] + c
                q.enqueue((d[v], v))

    return d[t]


def people_on_a_line(N: int, M: int, queries: list)->bool:
    E = [[] for _ in range(N)]
    for l, r, d in queries:
        cur_d = dijkstra(N, E, l-1, r-1)
        if cur_d == INF:
            E[l-1].append((r-1, d))
            E[r-1].append((l-1, d))
        else:
            if cur_d != d:
                return False
    return True


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]
    yes = people_on_a_line(N, M, queries)
    print('Yes' if yes else 'No')


### FIXED CODE ###

class WeightenedUnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size
        self.__diff_weight = [0] * size

    def find(self, u: int)->int:
        if self.__root[u] < 0:
            return u
        r = self.find(self.__root[u])
        self.__diff_weight[u] += self.__diff_weight[self.__root[u]]
        self.__root[u] = r
        return self.__root[u]

    def same(self, u: int, v: int)->bool:
        return self.find(u) == self.find(v)

    def unite(self, u: int, v: int, w: int):
        w += self.weight(u)
        w -= self.weight(v)

        x, y = self.find(u), self.find(v)

        if x == y:
            return

        if self.__root[y] < self.__root[x]:
            x, y = y, x
            w = -w

        self.__root[x] += self.__root[y]
        self.__root[y] = x

        self.__diff_weight[y] = w

    def weight(self, u: int)->int:
        self.find(u)
        return self.__diff_weight[u]

    def diff_weight(self, u: int, v: int)->int:
        return self.weight(v) - self.weight(u)


def people_on_a_line(N: int, M: int, queries: list)->bool:
    uf = WeightenedUnionFind(N)
    for l, r, d in queries:
        if uf.same(l-1, r-1):
            if d != uf.diff_weight(l-1, r-1):
                return False
        else:
            uf.unite(l-1, r-1, d)

    return True


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]
    yes = people_on_a_line(N, M, queries)
    print('Yes' if yes else 'No')
### BUGGY CODE ###

n, t = map(int, input().split())
a, b, ab = [], [], []
for _ in range(n):
    ab.append(tuple(map(int, input().split())))
ab.sort(key=lambda x:x[0])
for i in ab:
    a.append(i[0])
    b.append(i[1])

# dp[i][j] = 0~i番目の料理でj分以内に完食できる美味しさの合計の最大値
# 0 <= i < n-1, 0 <= j <= t-1
dp = [[0 for _ in range(min([t, a[0]]))] + [b[0] for _ in range(t-a[0])]]
for i in range(1, n-1):
    dp.append([])
    for j in range(min([t, a[i]])):
        dp[i].append(dp[i-1][j])
    for j in range(a[i], t):
        dp[i].append(max([dp[i-1][j], dp[i-1][j-a[i]]+b[i]]))

ans = []
for i in range(1, n):
    ans.append(dp[i-1][t-1] + b[i])
print(max(ans))

### FIXED CODE ###

n, t = map(int, input().split())
a, b, ab = [], [], []
for _ in range(n):
    ab.append(tuple(map(int, input().split())))
ab.sort(key=lambda x:x[0])
for i in ab:
    a.append(i[0])
    b.append(i[1])

# dp[i][j] = 0~i番目の料理でj分以内に完食できる美味しさの合計の最大値
# 0 <= i <= n-1, 0 <= j <= t-1
dp = [[0 for _ in range(min([t, a[0]]))] + [b[0] for _ in range(t-a[0])]]
for i in range(1, n):
    dp.append([])
    for j in range(min([t, a[i]])):
        dp[i].append(dp[i-1][j])
    for j in range(a[i], t):
        dp[i].append(max([dp[i-1][j], dp[i-1][j-a[i]]+b[i]]))

ans = []
for i in range(1, n):
    ans.append(dp[i-1][t-1] + b[i])
print(max(ans))
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]
S = [sum(A[:i]) for i in range(n+1)]
num = [S.count(i) for i in set(S)]
out = [i*(i-1)//2 for i in num if i>1]
print(sum(out))

### FIXED CODE ###

from collections import Counter
n = int(input())
A = [int(i) for i in input().split()]
S = [0]*(n+1)
for i in range(n):
    S[i+1] = S[i] + A[i]
def hello(data):
    dt = Counter()
    for i in data:
        dt[str(i)] += 1
    return dt
num = hello(S)
out = [i*(i-1)//2 for i in num.values() if i>1]
print(sum(out))
### BUGGY CODE ###

a, b, k = map(int, input().split())
data = [i for i in range(a, b + 1)]

if k >= -(-len(data)//2):
    for i in data:
        print(i)
else:
    for i in range(k):
        print(data[i])
    for i in range(len(data) - k, len(data)):
        print(data[i])

### FIXED CODE ###

a, b, k = map(int, input().split())
if k >= -(-(b - a + 1)//2):
    for i in range(a, b + 1):
        print(i)
else:
    for i in range(a, a + k):
        print(i)
    for i in range(b + 1 - k, b + 1):
        print(i)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=0
for i in range(n):
  ans+=sum(x<b[i] for x in a)*sum(x>b[i] for x in c)
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
ans=0
for i in range(n):
  d=bisect.bisect_left(a,b[i])
  e=bisect.bisect_right(c,b[i])
  ans+=d*(n-e)
print(ans)
### BUGGY CODE ###

from itertools import product as pd
f=lambda x,y:(x,y) if x<y else (y,x) 
n,k=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,c) in pd(range(n),repeat=2):
  for (b,d) in pd(range(n),repeat=2):
    lx,rx=f(o[a][0],o[b][0])
    dy,uy=f(o[c][1],o[d][1])
    cnt=0
    for i in o:
      if lx<=i[0]<=rx and dy<=i[1]<=uy:
        cnt+=1
    if cnt>=k:
      v=min(v,(rx-lx)*(uy-dy))
print(v)

### FIXED CODE ###

from itertools import combinations as comb
n,k=map(int,input().split())
f=lambda x,y:(min(x,y),max(x,y))
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,b) in comb(range(n),2):
  for (c,d) in comb(range(n),2):
    lx,rx=f(o[a][0],o[b][0])
    dy,uy=f(o[c][1],o[d][1])
    cnt=0
    for i in o:
      if lx<=i[0]<=rx and dy<=i[1]<=uy:
        cnt+=1
    if cnt>=k:
      v=min(v,(rx-lx)*(uy-dy))
print(v)
### BUGGY CODE ###

def resolve():


    from collections import deque

    n, m = map(int, input().split())
    ddp = deque(maxlen=2)

    li_broken = [0] * m
    for i in range(m):
        li_broken[i] = int(input())

    ddp.appendleft(0)
    ddp.appendleft(1)

    li_i = list(reversed(range(n)))

    for i in li_i:

        if i in li_broken:
            ddp.appendleft(0)

        else:
            ddp.appendleft(sum(ddp) % 1000000007)

    print(ddp[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)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for _ in range(Q):
    b, c = map(int, input().split())
    for i,v in enumerate(A):
        if v == b:
            A[i] = c
    print(sum(A))

### FIXED CODE ###

from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
d = defaultdict(int)
for key in A:
    d[key] += 1
d[sum] = sum(A)

Q = int(input())
for _ in range(Q):
    b, c = map(int, input().split())
    change_sum = d[b] * (c-b)
    d[sum] += change_sum
    d[c] += d[b]
    d[b] = 0
    print(d[sum])
### BUGGY CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
rs = [x - 1 for x in map(int, input().split())]
dist = [[float('inf')] * (N) for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    dist[A - 1][B - 1] = dist[B - 1][A - 1] = C
for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
ans = float('inf')
for p in permutations(rs):
    tmp = 0
    for i in range(R - 1):
        tmp += dist[p[i]][p[i + 1]]
        if tmp > ans:
            break
    else:
        ans = tmp
print(ans)

### FIXED CODE ###

from itertools import permutations
import sys
def main():
    N, M, R = map(int, input().split())
    rs = [x - 1 for x in map(int, input().split())]
    # グラフを作る
    dist = [[float('inf')] * (N) for _ in range(N)]
    for e in sys.stdin:
        A, B, C = map(int, e.split())
        dist[A - 1][B - 1] = dist[B - 1][A - 1] = C
    # ワーシャルフロイドで全頂点間距離算出
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    # 組み合わせ全探索
    ans = float('inf')
    for p in permutations(rs):
        tmp = 0
        for u, v in zip(p, p[1:]):
            tmp += dist[u][v]
            if tmp > ans:
                break
        else:
            ans = tmp
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
def print_ans(N, a_list):
    """Test Case
    >>> print_ans(3, [7, 6, 8])
    2
    >>> print_ans(3, [12, 15, 18])
    6
    >>> print_ans(2, [1000000000, 1000000000])
    1000000000
    """
    m_list = []
    a_list.append(0)
    for i in range(N):
        m = 0
        for k in range(i):
            m = gcd(max(m, a_list[k]), min(m, a_list[k]))
        for l in range(i + 1, N + 1):
            m = gcd(max(m, a_list[l]), min(m, a_list[l]))
        m_list.append(m)
    print(max(m_list))

if __name__ == '__main__':
    N = int(input().rstrip())
    a_list = list(map(int, input().rstrip().split()))
    print_ans(N, a_list)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from fractions import *
def print_ans(N, a_list):
    """Test Case
    >>> print_ans(3, [0, 7, 6, 8, 0])
    2
    >>> print_ans(3, [0, 12, 15, 18, 0])
    6
    >>> print_ans(2, [0, 1000000000, 1000000000,0])
    1000000000
    """
    l_list = [0 for _ in range(N + 2)]
    r_list = [0 for _ in range(N + 2)]
    for i in range(1, N + 1):
        l_list[i] = gcd(l_list[i-1], a_list[i])
    for i in range(N, 0, -1):
            r_list[i] = gcd(r_list[i + 1], a_list[i])
    m_list = [0 for _ in range(N + 1)]
    for i in range(1, N + 1):
        m_list[i] = gcd(l_list[i - 1],r_list[i+ 1])
    print(max(m_list))

if __name__ == '__main__':
    N = int(input().rstrip())
    a_list = [0] + list(map(int, input().rstrip().split())) + [0]
    print_ans(N, a_list)
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(100000) 

N = int(input())
*a, = map(int, input().split())

dp = [[-1] *  N for _ in range(N)]

def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    if i == j: 
        dp[i][j] = a[i]
        return a[i]
    ans = max(a[i] - rec(i+1, j), a[j] - rec(i, j-1))
    dp[i][j] = ans
    return ans

print(rec(0, N-1))

### FIXED CODE ###

N = int(input())
*a, = map(int, input().split())

dp = [[None] *  N for _ in range(N)]
for i in range(N): dp[i][i] = a[i]

for j in range(1, N):
    for i in range(j-1, -1, -1):
        dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1])

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

import sys
input = sys.stdin.readline
import numpy as np

n, k = map(int, input().split())
AA =[]
c =False
for a in input().strip().split():

    if not c:
        AA.append(int(a))
        if len(AA) == k:
            next = sum(AA)
            c = True
    else:
        base = next
        AA = AA[1:]
        AA.append(int(a))
        next = sum(AA)
        if next - base <= 0:
            print("No")
        else:
            print("Yes")


### FIXED CODE ###

n, k = map(int, input().split())
AA =[int(a) for a in input().split()]


for b, t in zip(AA, AA[k:]):
    if t > b:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

if 0 in a:
  print(0)
else:
  for i in a:
    u *=i
  if u > 1000000000000000000:
    print(-1)
  else:
    print(u)

    

    

  
  

### FIXED CODE ###

import sys
def main():
  u = 1  
  n = int(input())
  a = list(map(int,(input().split())))
  
  if 0 in a:
    print(0)
    sys.exit()
	
  for i in a:
    u *=i
    if u > 1000000000000000000:
      print(-1)
      sys.exit()

  print(u)


main()
### BUGGY CODE ###

from operator import itemgetter

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

b = [2, 5, 5, 4, 5, 6, 3, 7, 6]

c = []

for x in a:
    if x in [1, 4, 7, 8]:
        c.append((str(x), b[x - 1]))

if 5 in a:
    c.append(('5', 5))
elif 3 in a:
    c.append(('3', 5))
elif 2 in a:
    c.append(('2', 5))

if 9 in a:
    c.append(('9', 6))
elif 6 in a:
    c.append(('6', 6))

c = sorted(c, key=itemgetter(1), reverse=True)

dp = [0 for _ in range(n + 8)]

for x, y in c:
    dp[y] = int(x)

for i in range(2, n + 1):
    if dp[i] == 0:
        continue
    for x, y in c:
        dp[i + y] = max(dp[i + y], int(x + str(dp[i])))

print(dp[n])




### FIXED CODE ###

from operator import itemgetter

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

b = [2, 5, 5, 4, 5, 6, 3, 7, 6]

c = []

for x in a:
    if x in [1, 4, 7, 8]:
        c.append((x, b[x - 1]))

if 5 in a:
    c.append((5, 5))
elif 3 in a:
    c.append((3, 5))
elif 2 in a:
    c.append((2, 5))

if 9 in a:
    c.append((9, 6))
elif 6 in a:
    c.append((6, 6))

c = sorted(c, key=itemgetter(1), reverse=True)

dp = [-999999 for _ in range(n + 1)]
dp[0] = 0

for i in range(2, n + 1):
    for x, y in c:
        if i >= y:
            dp[i] = max(dp[i], dp[i - y] + 1)
    #print(i, dp)

c = sorted(c, key=itemgetter(0), reverse=True)

#print(c)
#print(dp)

s = []
k = dp[n]
while k > 0:
    #print(s, k)
    #input()
    for x, y in c:
        if n >= y:
            if dp[n - y] == k - 1:
                s.append(str(x))
                k -= 1
                n -= y
                break

print(int(''.join(s)))
### BUGGY CODE ###


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

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

ans = 0
for a in A:
    ans = max(ans, (A.count(a-1) + A.count(a) + A.count(a+1)))

print(ans)

### FIXED CODE ###


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

import collections

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

c = collections.Counter(A)

ans = 0
for a in A:
    tmp = c[a-1] + c[a] + c[a+1]
    ans = max(ans, tmp)

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

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

cnt = 0
for i in range(1000):
    si = str(i).zfill(3)
    k = 0
    for cn in range(n):
        if s[cn] == si[k]:
            if k == 2:
                cnt += 1
                break
            else:
                k += 1
print(cnt)


### FIXED CODE ###

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

cnt = 0
for i in range(1000):
    si = str(i).zfill(3)
    k = 0
    for cn in range(n):
        if s[cn] == si[k]:
            if k == 2:
                cnt += 1
                break
            else:
                k += 1
print(cnt)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

H, W = map(int, readline().split())
rW = range(W); rH = range(H)
S = [readline() for i in rH]
P = [[0]*W for i in rH]
for i in rH:
    p = -1
    Si = S[i]
    Pi = P[i]
    for j in rW:
        if Si[j] == '#':
            c = j - p - 1
            Pi[p+1:j] = (c for k in range(c))
            p = j
    c = W - p - 1
    Pi[p+1:W] = (c for k in range(c))
ans = 0
for j in rW:
    p = -1
    v = 0
    for i in rH:
        if S[i][j] == '#':
            ans = max(ans, v + (i - p - 1))
            v = 0
            p = i
        else:
            v = max(v, P[i][j])
    ans = max(ans, v + (H - p - 1))
sys.stdout.write("%d\n" % (ans - 1))

### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for i in range(H)]
P = [[0]*W for i in range(H)]
Q = [[0]*W for i in range(H)]
for i in range(H):
    p = -1
    for j in range(W):
        if S[i][j] == '#':
            c = j - p - 1
            for k in range(p+1, j):
                P[i][k] = c
            p = j
    c = W - p - 1
    for k in range(p+1, W):
        P[i][k] = c
for j in range(W):
    p = -1
    for i in range(H):
        if S[i][j] == '#':
            c = i - p - 1
            for k in range(p+1, i):
                Q[k][j] = c
            p = i
    c = H - p - 1
    for k in range(p+1, H):
        Q[k][j] = c
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            ans = max(ans, P[i][j] + Q[i][j])
print(ans - 1)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

def f(j, max1, max2):
    L_temp = L[j+1:]
    # print("max1 = ", max1, "max2 = ", max2, L_temp)
    dif = max1 - max2
    left = -1
    right = len(L_temp)
    while right - left != 1:
        temp = (left+right)//2
        if dif < L_temp[temp]:
            left = temp
        else:
            right = temp
    if left != N:
        return left+1
    else:
        return left


ans = 0
max1 = 0
max2 = 0
for i in range(N):
    max1 = L[i]
    for j in range(i+1, N-1):
        max2 = L[j]
        ans += f(j, max1, max2)
        # print("ans = ", ans)
print(ans)


### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

def f(j, max1, max2):
    L_temp = L[j+1:]
    # print("max1 = ", max1, "max2 = ", max2, L_temp)
    dif = max1 - max2
    left = -1
    right = len(L_temp)
    while right - left != 1:
        temp = (left+right)//2
        if dif < L_temp[temp]:
            left = temp
        else:
            right = temp
    if left != N:
        return left+1
    else:
        return left


ans = 0
max1 = 0
max2 = 0
for i in range(N):
    max1 = L[i]
    for j in range(i+1, N-1):
        max2 = L[j]
        ans += f(j, max1, max2)
        # print("ans = ", ans)
print(ans)
### BUGGY CODE ###

from heapq import heappush, heappop

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

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

cost = [float('inf')]*(H+1)

q = [(0, 0)]

while q:
    c, t = heappop(q)
    if t >= H:
        cost[H] = c
        break
    if cost[t] <= c:
        continue

    cost[t] = c
    for a,b in AB:
        heappush(q, (b+c, t+a))

print(cost[H])

### FIXED CODE ###

min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())


dp = [float('inf')]*(H+1)
dp[0] = 0

for _ in range(N):
    a,b = map(int,input().split())
    for i,v in enumerate(dp):
        j = min2(H,i+a)
        dp[j] = min2(dp[j],v+b)

print(dp[-1])