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

n = int(input())
s = input()
M = 10**9 + 7

def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[None] * n for _ in range(n)]
def dfs(zk, i=0):
    if dp[zk][i] is not None:
        return dp[zk][i]

    if i == n - 1:
        dp[zk][i] = 1
        return 1

    zj = n - i - zk - 1
    cnt = 0

    if s[i] == "<":
        for v in range(zk):
            cnt += dfs(v, i + 1)
    else:
        for v in range(zj):
            cnt += dfs(zk + v, i + 1)
    dp[zk][i] = cnt
    return cnt

def cumsum(array):
    array = array[:]
    for i in range(len(array) - 1):
        array[i + 1] = mod(array[i + 1] + array[i])
    array.append(0)
    return array

for i in reversed(range(n)):
    for zk in range(n):
        if i == n - 1:
            dp[i][zk] = 1
            continue

        zj = n - i - zk - 1
        cnt = 0

        if s[i] == "<":
            # for v in range(zk):
            #     # cnt = mod(cnt + dp[i + 1][v])
            cnt = cs[zk - 1]
        else:
            # for v in range(zj):
            #     # cnt = mod(cnt + dp[i + 1][zk + v])
            cnt = cs[zk + zj - 1] - cs[zk - 1]
        dp[i][zk] = cnt
    cs = cumsum(dp[i])

print(sum(dp[0]) % M)


### FIXED CODE ###

n = int(input())
s = input()
M = 10**9 + 7

def mod(v):
    if v >= M:
        return v % M
    return v


dp = [[1] * n + [0] for _ in range(2)]
s = [v == "<" for v in s]
for i in reversed(range(n - 1)):
    for j in range(n - 1):
        dp[1][j + 1] = dp[1][j + 1] + dp[1][j]
        dp[0][j] = dp[1][j]
    dp[0][-2] = dp[1][-2]

    for zk in range(n - i):
        cnt = 0

        if s[i]:
            cnt = dp[0][zk - 1]
        else:
            zj = n - i - zk - 1
            cnt = dp[0][zk + zj - 1] - dp[0][zk - 1]
        dp[1][zk] = mod(cnt)

print(sum(dp[1]) % M)
### BUGGY CODE ###

#A - AKIBA △
S = input()
S = list(S)

SS = []
for p in S:#Aを追加する空白を作る
    SS.append('')
    SS.append(p)
SS.append('')


result = 'NO'
if len(S) <= 9 and 'K' in S and 'I' in S and 'H' in S and 'B' in S and 'R' in S:
    for i in range(1<<(len(SS))):
        SSS = SS.copy()
        for j in range(len(SS)):
            mask = 1 << j
            if mask & i != 0:#処理を行う
                if SSS[j] == '':
                    SSS[j] = 'A'
        for k in SSS:
            if k == '':
                SSS.remove('')
        if SSS == ['A','K','I','H','A','B','A','R','A']:
            result = 'YES'
print(result)

### FIXED CODE ###

#A - AKIBA △
S = input()
S = list(S)

SS = []
for p in S:#Aを追加する空白を作る
    SS.append('')
    SS.append(p)
SS.append('')


result = 'NO'
if len(S) <= 9 and 'K' in S and 'I' in S and 'H' in S and 'B' in S and 'R' in S:
    for i in range(1<<(len(SS))):
        SSS = SS.copy()
        for j in range(len(SS)):
            mask = 1 << j
            if mask & i != 0:#処理を行う
                if SSS[j] == '':
                    SSS[j] = 'A'
        for k in SSS:
            if k == '':
                SSS.remove('')
        if SSS == ['A','K','I','H','A','B','A','R','A']:
            result = 'YES'
print(result)
### BUGGY CODE ###

import copy

class UnionFind:
	def __init__(self, N):
		self._parent = [i for i in range(N)]

	def find(self, x):
		if self._parent[x] == x:
			return x
		else:
			return self.find(self._parent[x])

	def unite(self, a, b):
		ta = self.find(a)
		tb = self.find(b)
		if(ta == tb):
			return
		self._parent[ta] = tb # make b as a parent of a
			
	def check(self, a, b):
		return self.find(a) == self.find(b)
		
if __name__ == '__main__':
	N,K,L = map(int, input().split())
	uf1 = UnionFind(N)
	for _ in range(K):
		p,q = map(int, input().split())
		uf1.unite(p-1,q-1)
	uf2 = UnionFind(N)
	for _ in range(L):
		s,r = map(int, input().split())
		uf2.unite(s-1,r-1)
	from collections import defaultdict
	d = defaultdict(int)
	for i in range(N):
		d[(uf1.find(i), uf2.find(i))] += 1
	ans = []
	for i in range(N):
		ans.append( str(d[(uf1.find(i), uf2.find(i))]) )
	print(' '.join(ans))

### FIXED CODE ###

import copy

class UnionFind:
	def __init__(self, N):
		self._parent = [i for i in range(N)]

	def find(self, x):
		if self._parent[x] == x:
			return x
		else:
			return self.find(self._parent[x])

	def unite(self, a, b):
		ta = self.find(a)
		tb = self.find(b)
		if(ta != tb):
			self._parent[ta] = min(ta,tb)
			self._parent[tb] = self._parent[ta]
		
			
	def check(self, a, b):
		return self.find(a) == self.find(b)
		
if __name__ == '__main__':
	N,K,L = map(int, input().split())
	uf1 = UnionFind(N)
	for _ in range(K):
		p,q = map(int, input().split())
		uf1.unite(p-1,q-1)
	uf2 = UnionFind(N)
	for _ in range(L):
		s,r = map(int, input().split())
		uf2.unite(s-1,r-1)
	from collections import defaultdict
	d = defaultdict(int)
	for i in range(N):
		d[(uf1.find(i), uf2.find(i))] += 1
	ans = []
	for i in range(N):
		ans.append( str(d[(uf1.find(i), uf2.find(i))]) )
	print(' '.join(ans))
### BUGGY CODE ###

import math
import random

def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False
    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1
        if y != n - 1 and t & 1 == 0:
            return False
    return True

def sqrt2(n):
    if is_prime(n):
        return (n, 1)
    start = round(math.sqrt(n))
    i = 0
    while True:
        if n % (start + i) == 0:
            return (start + i), n // (start + i)
        i += 1
    return (0, 0)

N = int(input())
a, b = sqrt2(N)
print(a + b - 2)


### FIXED CODE ###

import math

def sq(n):
    for i in range(math.ceil(math.sqrt(N)), -1, -1):
        if n % i == 0:
            return (i, n//i)

N = int(input())
a, b = sq(N)
print(a + b - 2)
### BUGGY CODE ###

# coding:utf-8

INF = float('inf')


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


N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A)

count = 0
for i in range(N):
    tmp = B.index(A[i])
    diff = abs(i - tmp)
    if diff % 2 == 1:
        count += 1

print(count // 2)


### FIXED CODE ###

# coding:utf-8

INF = float('inf')


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


N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A)
C = A[::2] + B[1::2]
D = set(C)

print(N - len(D))
### BUGGY CODE ###

from math import ceil
A,B,C,D,E,F = map(int,input().split())

W,S = [],[0]
limW,limS = 3000,3000

for ai in range(ceil(limW/A)):
    for bi in range(ceil(limW/B+1)):
        w = 100*A*ai+100*B*bi
        if w <= limW and 0 < w and w not in W:
            W.append(w)
for ci in range(ceil(limS/C)):
    for di in range(ceil(limS/D)):
        s = C*ci+D*di
        if s <= limS and 0 < s and s not in S:
            S.append(s)

AnsWS,AnsS,r = 0,0,-1
for wi in W:
    for si in S:
        if r < si/wi and si <= E*(wi//100) and (wi+si) <= F:
            AnsWS,AnsS,r = wi+si,si,si/wi

print(AnsWS,AnsS)

### FIXED CODE ###

from math import ceil
A,B,C,D,E,F = map(int,input().split())

W,S = [],[0]

for ai in range(ceil(F/A)):
    for bi in range(ceil(F/B)):
        w = 100*A*ai+100*B*bi
        if w <= F and 0 < w and w not in W:
            W.append(w)
for ci in range(ceil(F/C)):
    for di in range(ceil(F/D)):
        s = C*ci+D*di
        if s <= F and 0 < s and s not in S:
            S.append(s)

AnsWS,AnsS,r = 0,0,-1
for wi in W:
    for si in S:
        if r < si/wi and si <= E*(wi//100) and (wi+si) <= F:
            AnsWS,AnsS,r = wi+si,si,si/wi

print(AnsWS,AnsS)
### BUGGY CODE ###

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

lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr += (list(range(l, r + 1)))

lr.sort()

dp = [0] * n

dp[0] = 1

for i in range(n - 1):
    for k in lr:
        if i + 1 - k >= 0:
            dp[i + 1] += dp[i + 1 - k]
            dp[i + 1] %= MOD

print(dp[-1])

### FIXED CODE ###

def solve(l, r, i):
    if i - l < 1:
        return 0
    return dp[i - l] - dp[max(i - r - 1, 0)]


n, k = map(int, input().split())
MOD = 998244353
lr = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n + 1)
dp[1] = 1

for i in range(2, n + 1):
    tmp = 0
    for l, r in lr:
        tmp += solve(l, r, i)
    tmp = tmp % MOD
    dp[i] = (dp[i - 1] + tmp) % MOD

print(tmp)
### BUGGY CODE ###

A,B,C,K = map(int,input().split())
N = [A,B,C]
N2 = N.copy()
for i in range(K):
    N2[0] = N[1] + N[2]
    N2[1] = N[0] + N[2]
    N2[2] = N[0] + N[1]
    N = N2.copy()
ans = N2[0] - N2[1]
if abs(ans) > 10**18:
    print('Unfair')
else:
    print(ans)

### FIXED CODE ###

a,b,c,k = map(int, input().split())
cheak = 10**18
ans = a-b
def calc(a,b,c,k):
    if a == b:
        return 0
    elif ans < 0:
        if k % 2 == 1:
            return -ans
        else:
            return ans
    else:
        if k % 2 == 1:
            return -ans
        else:
            return ans
ans_n = calc(a,b,c,k)
if ans_n > cheak:
    print("Unfair")
else:
    print(ans_n)
### BUGGY CODE ###

n = int(input())
for _ in range(n):
    a, b = input(), input()
    i, j = len(a), len(b)
    prev = [0] * (j + 1)
    for ca in a:
        cur = [0] * (j + 1)
        cl = -1
        for l, cb in enumerate(b):
            if ca == cb:
                cur[l + 1] = cl = prev[l] + 1
            else:
                cur[l + 1] = cl = max(cl, prev[l + 1])
        prev = cur
    print(prev[-1])

### FIXED CODE ###

n = int(input())
for _ in range(n):
    a, b = input(), input()
    indices = []
    for cb in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(indices):
            chr_idx = a.find(cb, bgn_idx) + 1
            if not chr_idx:
                break
            if chr_idx < cur_idx:
                indices[i] = chr_idx
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                indices.append(chr_idx)
    print(len(indices))
### BUGGY CODE ###

#ABC055

n = int(input())
p = 10 ** 9 + 7
x = 1
for i in range(1,n):
    x *= (i + 1) % p
print(x % p)

### FIXED CODE ###

#ABC055

n = int(input())
p = 10 ** 9 + 7
x = 1
for i in range(1,n):
    x *= (i + 1) % p
    x %= p
print(x % p)
### BUGGY CODE ###

L,R = map(int,input().split())
#divisor = [2019,673,3]
x = 2019
if L-R >= 2019:
    x=0
else:
    for i in range(L,R):
        for j in range(i+1,R+1):
            #x = min(x,(i%2019)*(j%2019))
            x = min(x,(i*j)%2019)

print(x)

### FIXED CODE ###

L,R = map(int,input().split())
 
x = 2019**2
for i in range(L, R):
    for r in range(i+1, R+1):
        ans = (i*r) % 2019 
        if x > ans:
            x = ans
            if x == 0:
        	    break
    if x == 0:
      break
print(x)
### BUGGY CODE ###

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

answer = max(A, B)
while True:
    if answer % A == 0 and answer % B  == 0:
        break
    answer += 1

print(answer)

### FIXED CODE ###

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

multiply = 1
while True:
    if A * multiply % B  == 0:
        break
    multiply += 1

answer = A * multiply

print(answer)
### BUGGY CODE ###

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7

#    print(A)
#    print(A_plus)
#    print(A_minus)
if N == K:
    ans = 1
    for i in A:
        ans *= i % mod
    print(ans % mod)

elif A[-1] < 0:
    ans = 1
    for i in range(K):
        ans *= A[-(i + 1)] % mod
    print(ans % mod)

elif K % 2 == 0:
    ans = 1
    j = 0
    i = N - 1
    for _ in range(K // 2):
        if A[j] * A[j + 1] > A[i] * A[i - 1]:
            ans *= A[j] * A[j + 1]
            ans %= mod
            j += 2
        else:
            ans *= A[i] * A[i - 1]
            ans %= mod
            i -= 2
    print(ans % mod)

else:
    ans = A[-1]
    j = 0
    i = N - 2
    for _ in range(K // 2):
        if A[j] * A[j + 1] > A[i] * A[i - 1]:
            ans *= A[j] * A[j + 1]
            ans %= mod
            j += 2
        else:
            ans *= A[i] * A[i - 1]
            ans %= mod
            i -= 2
    print(ans % mod)


### FIXED CODE ###

import sys

# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
# import heapq
import bisect


# def input():
#     return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    mod = 10 ** 9 + 7

    if N == K:
        ans = 1
        for i in range(N):
            ans *= A[i]
            ans %= mod
        print(ans % mod)



    elif K % 2 == 0:
        ans = 1
        j = 0
        i = N - 1
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)

    elif A[-1] < 0:
        ans = 1
        for i in range(K):
            ans *= A[-(i + 1)]
            ans %= mod
        print(ans % mod)
    else:
        ans = A[-1]
        j = 0
        i = N - 2
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)


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

n = int(input())
freq = []
slst = []
sset = set()
for i in range(n):
  temp = input()
  if temp not in sset:
    slst.append(temp)
    sset.add(temp)
    freq.append(0)
  else:
    freq[slst.index(temp)] += 1
fmax = max(freq)
mflst = []
for i in range(len(freq)):
  if freq[i] == fmax:
    mflst.append(slst[i])
mflst.sort()
for i in range(len(mflst)):
  print(mflst[i])

### FIXED CODE ###

n = int(input())
#freq = []
#slst = []
dic1 = {}
for i in range(n):
  temp = input()
  dic1.setdefault(temp, 0)
  dic1[temp] += 1
fmax = max(dic1.values())
mflst = []
ks = list(dic1.keys())
for i in dic1:
  if dic1[i] == fmax:
    mflst.append(i)
    
mflst.sort()
for i in range(len(mflst)):
  print(mflst[i])
### BUGGY CODE ###

s=input()
c=0
for i in range(len(s)):
    for j in range(i,len(s)):
        z = s[i:j+1]
        if int(z) %2019==0:
            c += 1

print(c)
        

### FIXED CODE ###

S = input()
N = len(S)
A = [int(S[i]) for i in range(N)]
A = A[::-1]

MOD = 2019

p10 = [1] * N
for i in range(1, N):
	p10[i] = (p10[i - 1] * 10) % MOD

for i in range(N):
	A[i] = (A[i] * p10[i]) % MOD

cumsum = [A[0]] * N
for i in range(1, N):
	cumsum[i] = (cumsum[i - 1] + A[i]) % MOD

cnt = [0] * MOD
cnt[0] = 1
for i in range(N):
	cnt[cumsum[i]] += 1

ans = 0
for i in range(MOD):
	ans += cnt[i] * (cnt[i] - 1) // 2

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

from queue import PriorityQueue as PQ

INF = float('inf')
yen = 10**15

def pcc(src, adj):
	global n
	pq = PQ()
	dist = [INF]*(n+1)
	dist[src] = 0
	pq.put([0,src])
	while not pq.empty():
		d,u = pq.get()
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				pq.put([dist[v], v])
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = {}
adjt = {}
for i in range(n+1):
	adjs[i] = []
	adjt[i] = []
for i in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)

tab = [0]*(n+1)
for i in range(1,n+1):
	tab[i] = dist_s[i] + dist_t[i]
	# ~ print("echange",i," = ",tab[i])
	# ~ tab[i] = yen - tab[i]

ans = [0]*(n+1)
ans[n] = tab[n]
for i in range(n-1,0,-1):
	ans[i] = min(ans[i+1], tab[i])
	
for i in range(n):
	print(yen - ans[i+1])


### FIXED CODE ###

import heapq
def dijkstra(s, neighbor):
	dist = [float('inf')] * N
	dist[s] = 0
	que = [(0, s)]
	heapq.heapify(que)
	while que:
		d, v = heapq.heappop(que)
		if d > dist[v]:
			continue
		for u, l in neighbor[v]:
			tmp_d = d + l
			if tmp_d < dist[u]:
				dist[u] = tmp_d
				heapq.heappush(que, (tmp_d, u))
	return dist
 
N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
	u, v, a, b = map(int, input().split())
	yen[u-1].append((v-1, a))
	yen[v-1].append((u-1, a))
	snuuk[u-1].append((v-1, b))
	snuuk[v-1].append((u-1, b))
 
dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
	if dist_s[i] + dist_t[i] < tmp:
		tmp = dist_s[i] + dist_t[i]
	ans[i] = 10 ** 15 - tmp
print(*ans, sep='\n')
### BUGGY CODE ###

import sys

def main():
    S = list(input())
    a = []
    for i in range(0, len(S) + 1):
        a.append(calc(i, S))
    
    total = 0
    for i in range(0, len(a)):
        total += a[i]
    
    print(total)

def calc(i, S):
    if i == 0:
        if S[i] == '<':
            return 0
        else:
            j = 0
            while j < len(S) and S[j] == '>':
                j += 1
            return j
    elif i == len(S):
        if S[i - 1] == '>':
            return 0
        else:
            j = 0
            while j < len(S) and S[i - 1 - j] == '<':
                j += 1
            return j
    else:
        j = 0
        while j < i and S[i - 1 - j] == '<':
            j += 1
        k = 0
        while (i + k) < len(S) and S[i + k] == '>':
            k += 1
        return max(j, k)

main()


### FIXED CODE ###

def main():
    S = list(input())
    N = len(S) + 1
    a = [-1] * N
    for i in range(N):
        if a[i] == -1:
            calc(i, S, a)

    print(sum(a))

def calc(i, S, a):
    if i == 0:
        if S[i] == '<':
            a[i] = 0
        else:
            j = 0
            while j < len(S) and S[j] == '>':
                j += 1
            for k in range(j):
                a[k] = j - k
    elif i == len(S):
        if S[i - 1] == '>':
            a[i] = 0
        else:
            a[i] = a[i - 1] + 1
    else:
        if S[i - 1] == '<' and S[i] == '<':
            a[i] = a[i - 1] + 1
        elif S[i - 1] == '<' and S[i] == '>':
            j = 0
            while (i + j) < len(S) and S[i + j] == '>':
                j += 1
            for l in range(j):
                a[i + l] = j - l
            a[i] = max(a[i - 1] + 1, j)
        elif S[i - 1] == '>' and S[i] == '<':
            a[i] = 0
        elif S[i - 1] == '>' and S[i] == '>':
            a[i] = a[i - 1] - 1

main()
### BUGGY CODE ###

import math
n=int(input())
k=int(input())

sum=0
for i in range(1,n+1):
    a=list(str(i))
    b=(math.log(i,10)//1)
    if a.count('0')==(b+1-k):
        sum+=1

print(sum)

### FIXED CODE ###

n=input()
k=int(input())
m=len(n)
dp=[[[0]*(k+1) for _ in range(2)] for _ in range(m+1)]
dp[0][0][0]=1
for i in range(1,m+1):
    l = int(n[i-1])
    for j in range(k+1):
        dp[i][1][j]+=dp[i-1][1][j] 
        if l!=0:
            dp[i][1][j]+=dp[i-1][0][j]  
        else:
            dp[i][0][j]+=dp[i-1][0][j]      
        if j-1>=0:
            dp[i][1][j]+=9*dp[i-1][1][j-1]
            if l!=0:
                dp[i][0][j]+=dp[i-1][0][j-1]
                dp[i][1][j]+=(l-1)*dp[i-1][0][j-1]
print(dp[m][0][k]+dp[m][1][k])
### BUGGY CODE ###

import bisect
N,Q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(N)]
STX.sort(key=lambda x:x[2])
ans=[-1]*Q
jump=[-1]*Q
D=[int(input()) for i in range(Q)]
for s,t,x in STX:
    l=bisect.bisect_left(D,s-x)
    r=bisect.bisect_left(D,t-x)
    while(l<r):
        k=jump[l]
        if k==-1:
            ans[l]=x
            jump[l]=r
            l+=1
        else:
            l=k
for i in range(Q):
    print(ans[i])


### FIXED CODE ###

import bisect
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(N)]
STX.sort(key=lambda x:x[2])
ans=[-1]*Q
jump=[-1]*Q
D=[int(input()) for i in range(Q)]
for s,t,x in STX:
    l=bisect.bisect_left(D,s-x)
    r=bisect.bisect_left(D,t-x)
    while(l<r):
        k=jump[l]
        if k==-1:
            ans[l]=x
            jump[l]=r
            l+=1
        else:
            l=k
for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
li = []
count = 0
for i in range(n):
    sli = sorted(list(input()))
    s = "".join(sli)
    if s in li:
        count += li.count(s)
    li.append(s)
print(count)

### FIXED CODE ###

n = int(input())
d = {}
count = 0
for i in range(n):
    sli = sorted(list(input()))
    s = "".join(sli)
    if s in d:
        count += d[s]
        d[s] += 1
    else:
        d[s] = 1
print(count)
### BUGGY CODE ###

s=input()
x,y=map(int,input().split())
xpossible=[0]
ypossible=[0]
j=0
while s[j]=='F':
  xpossible[0]+=1
  if j==len(s):
    break
counter=0
for i in range(j,len(s)):
  current=0
  while s[i]=='F':
    current+=1
    if i==len(s):
      break
  r=set()
  if counter==0:
    for j in xpossible:
      r.add(j+current)
      r.add(j-current)
    xpossible=[]
    for j in r:
      xpossible.append(j)
  else:
    for j in ypossible:
      r.add(j+current)
      r.add(j-current)
    ypossible=[]
    for j in r:
      ypossible.append(j)
  current=0
  while s[i]=='T':
    current+=1
  counter=(counter+current)%2
if x in xpossible and y in ypossible:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s=input()
x,y=map(int,input().split())
xpossible=[0]
ypossible=[0]
j=0
while s[j]=='F':
  j+=1
  xpossible[0]+=1
  if j==len(s):
    break
counter=0
i=j
while i<len(s):
  current=0
  while s[i]=='F':
    i+=1
    current+=1
    if i==len(s):
      break
  r=set()
  if counter==0:
    for j in xpossible:
      r.add(j+current)
      r.add(j-current)
    xpossible=[]
    for j in r:
      xpossible.append(j)
  else:
    for j in ypossible:
      r.add(j+current)
      r.add(j-current)
    ypossible=[]
    for j in r:
      ypossible.append(j)
  if i==len(s):
    break
  current=0
  while s[i]=='T':
    i+=1
    current+=1
    if i==len(s):
      break
  counter=(counter+current)%2
if x in xpossible and y in ypossible:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

def solve():
    N, M = map(int, input().split())
    A = []
    B = []
    dp = [float('inf')] * (N + 30000)
    dp[0] = 0
    for _ in range(M):
        a, b = list(map(int, input().split()))
        for i in range(N + 10000):
            if dp[i] == 'inf':
                continue
            dp[i+a] = min(dp[i+a], dp[i] + b)
        
    return min(dp[N:])

print(solve())

### FIXED CODE ###

import numpy as np

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

A = []
B = []
for i in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

A = np.array(A)
B = np.array(B)

dp = np.full((H+1), np.inf)
dp[0] = 0

def solve():
    for i in range(1, H + 1):
        dp[i] = np.amin(dp[np.maximum(i - A , 0)] + B)
    return int(dp[H])

print(solve())