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

from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        else:
            warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])
wroute = deque()

while route:
    while route:
        y, x = route.popleft()
        wroute.append([y, x])
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        else:
            warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])
wroute = deque()

while route:
    while route:
        y, x = route.popleft()
        wroute.append([y, x])
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])
### BUGGY CODE ###

def main():
    n = int(input())
    s = list(input())

    if n <= 3:
        print(0)
        exit()
    r = 0
    for ia in range(0,n-3):
        ta = s[ia]
        for ib in range(ia+1, n-1):
            tb = s[ib]
            t = (ta, tb)
            sa = ib - ia
            if ta == tb:
                pass
            else:
                cnt = 1
                ts = s[ib+1:]
                for ets in ts:
                    if cnt == sa:
                        pass
                    elif not ets in t:
                        r += 1
                    cnt += 1
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    s = list(input())
    sr = [0] * n
    sg = [0] * n
    sb = [0] * n
    for i1 in range(n):
        ts = s[i1]
        if ts == 'R':
            sr[i1] = 1
        elif ts == 'G':
            sg[i1] = 1
        else:
            sb[i1] = 1
    if n <= 3:
        print(0)
        exit()
    r = 0
    for ia in range(0,n-3):
        ta = s[ia]
        if ta == 'R':
            r += sum(sg[ia+1:]) * sum(sb[ia+1:])
        elif ta == 'G':
            r += sum(sr[ia+1:]) * sum(sb[ia+1:])
        else:
            r += sum(sg[ia + 1:]) * sum(sr[ia + 1:])
        for ib in range((n - ia)//2+1):
            if ia + ib * 2 < n:
                if ta != s[ia + ib] and ta != s[ia + ib + ib] and s[ia+ib]!= s[ia + ib + ib]:
                    r -= 1
    print(r)

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

#!/usr/bin/env python
# -*- coding:utf-8 -*-

import sys

coin = [1, 5, 10, 50, 100, 500]

def charge(remain):
	ch = [0] * 6
	index = 5
	while remain > 0:
		while remain >= coin[index]:
			ch[index] += 1
			remain -= coin[index]
		index -= 1
	return ch

def total_coins(n):
	sum = 0
	for i in range(6):
		sum += n[i] * coin[i]
	return sum
	
def compute(p, n):
	a = n
	remain = p
	
	pay = [0] * 6
	index = 5
	while remain > 0:
		while remain >= coin[index]:
			if a[index] > 0:
				pay[index] += 1
				a[index] -= 1
				remain -= coin[index]
		index -= 1
	ch = charge(remain)
	cand = [sum(pay)+sum(ch)]

	for i in range(5, 0, -1):
		b = a
		pay2 = pay
		if b[i] > 0:
			pay2[i] += 1
			for j in range(i):
				pay2[j] = 0
			total = total_coins(pay2)
			ch = charge(total - p)
			cand.append(sum(pay2) + sum(ch))
	
	return min(cand)

	
if __name__ == '__main__':
	for input in sys.stdin:
		input = map(int, input.split())
		p, n = input[0], input[1:]
		if p == 0:
			break
		print compute(p, n)
		

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-

import sys

coin = [1, 5, 10, 50, 100, 500]

def charge(remain):
	if remain == 0:
		return [0] * 6
	ch = [0] * 6
	index = 5
	while remain > 0:
		while remain >= coin[index]:
			ch[index] += 1
			remain -= coin[index]
		index -= 1
	return ch

def compute(p, n):
	candidates = []
	for r in range(500):
		pay = [0] * 6
		q = p + r
		for i in range(5, -1, -1):
			m = q / coin[i]
			pay[i] = min(m, n[i])
			q -= pay[i] * coin[i]
		if q == 0:
			candidates.append(sum(pay) + sum(charge(r)))
	return min(candidates)
	
if __name__ == '__main__':
	for input in sys.stdin:
		input = map(int, input.split())
		p, n = input[0], input[1:]
		if p == 0:
			break
		print compute(p, n)
### BUGGY CODE ###

from collections import Counter
from fractions import gcd
a, b = map(int, input().split())
n = int(max(a, b)**(1/2)) + 1
prime_num_cnt = [0]*(n + 1)
prime_num = []
for i in range(2, n+1):
    if prime_num_cnt[i] == 0:
        prime_num.append(i)
        tmp = i
        for j in range(1, n):
            if tmp*j > n:
                break
            prime_num_cnt[tmp*j] = 1


g = gcd(max(a, b), min(a, b))
cnt = Counter()
m = 2
while m <= g:
    while g % m == 0:
        g //= m
        cnt[m] += 1
    m += 1

print(len(cnt) + 1)


### FIXED CODE ###

from collections import Counter
from fractions import gcd
a, b = map(int, input().split())
n = int(max(a, b)**(1/2)) + 1

g = gcd(a, b)
cnt = Counter()
m = 2
while m*m<= g:
    while g % m == 0:
        g //= m
        cnt[m] += 1
    m += 1
if g > 1:
    cnt[g] += 1

print(len(cnt) + 1)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]

result = 1

for x in range(N):
    result = result * A[x]
if result >= 10**18 + 1:
    print(-1)
else:
    print(result)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]

result = 1

if A.count(0) == 0:
    for x in range(N):
        result = result * A[x]
        if result >= 10**18 + 1:
            print(-1)
            exit()
    print(result)
else:
    print(0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


h, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
diff = [[0]*(w+1) for i in range(h+1)]

for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

n = 80 * 70 + 1
dp = [[False]*n for i in range(h*w)]
dp[0][diff[0][0]] = True

for k in range(h*w):
    for cnt in range(n):
        if dp[k][cnt]:
                i = k // w
                j = k % w
                tmp1 = diff[i+1][j]
                tmp2 = diff[i][j+1]
                if i+1 < h:
                    dp[k + w][abs(cnt - tmp1)] = True
                    if cnt + tmp1 < n:
                        dp[k + w][cnt + tmp1] = True

                if j+1 < w:
                    dp[k + 1][abs(cnt - tmp2)] = True 
                    if cnt + tmp2 < n:
                        dp[k + 1][cnt + tmp2] = True

for i, boo in enumerate(dp[w*h - 1][0:81]):
    if boo:
        print(i)
        exit()
print(a[10*9])

### FIXED CODE ###

import sys
input = sys.stdin.readline


h, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]

diff = [[0]*(w) for i in range(h)]
for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

dp = [0] * (h*w)
dp[0] |= 1 << (13000 + diff[0][0])
dp[0] |= 1 << (13000 - diff[0][0])

for k in range(h*w):
    i = k // w
    j = k % w
    if i+1 < h:
        tmp1 = diff[i+1][j]
        dp[k + w] |= dp[k] << tmp1
        dp[k + w] |= dp[k] >> tmp1       
    if j+1 < w:
        tmp2 = diff[i][j+1]
        dp[k + 1] |= dp[k] << tmp2
        dp[k + 1] |= dp[k] >> tmp2


ans = 10**9
for i in range(81):
    if dp[w*h - 1] >> 13000 + i & 1:
        ans = min(ans, i)
for i in range(81):
    if dp[w*h - 1] >> 13000 - i & 1:
        ans = min(ans, i) 
print(ans)
### BUGGY CODE ###

h, w, k = map(int, input().split())
s = [input() for _ in range(h)]
cum_s = [[0 for _ in range(w+1)] for _ in range(h)]
for i in range(1, w+1):
    for j in range (h):
        cum_s[j][i] += (s[j][i-1] == '1') + cum_s[j][i-1]
#print(cum_s)

ans = 10 ** 6
for i in range(2 ** (h-1)):
    sep = []
    tmp = [0]
    for j in range(h-1):
        if (i >> j) & 1:
            tmp.append(j+1)
        else:
            if tmp != []:
                sep.append(tmp)
            tmp = [j+1]
    sep.append(tmp)
    #print(sep)
    
    idx = 0
    cnt = 0
    for j in range(1,w+1):
        flg = False
        for l in sep:
            tmp_sum = sum([cum_s[x][j] - cum_s[x][idx] for x in l])
            if tmp_sum > k:
                flg = True
        
        if flg:
            cnt += 1
            idx = j-1 
    #print(len(sep)-1, cnt)
    ans = min(ans, len(sep)-1 + cnt)
        
print(ans)

### FIXED CODE ###

h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

cum_s = [[0 for _ in range(w+1)] for _ in range(h)]
for i in range(1, w+1):
    for j in range (h):
        cum_s[j][i] += (s[j][i-1] == '1') + cum_s[j][i-1]
#print(cum_s)

ans = 10 ** 6
for i in range(2 ** (h-1)):
    sep = []
    tmp = [0]
    for j in range(h-1):
        if (i >> j) & 1:
            tmp.append(j+1)
        else:
            if tmp != []:
                sep.append(tmp)
            tmp = [j+1]
    sep.append(tmp)
    #print(sep)
    
    idx = 0
    cnt = 0
    for j in range(1,w+1):
        flg = False
        for l in sep:
            tmp_sum = sum([cum_s[x][j] - cum_s[x][idx] for x in l])
            if tmp_sum > k:
                if j - idx == 1:
                    cnt = 10 ** 6
                flg = True
        
        if flg:
            cnt += 1
            idx = j-1 
    #print(len(sep)-1, cnt)
    ans = min(ans, len(sep)-1 + cnt)

if w == 1:
    x = sum([s[i] == '1' for i in range(h)])
    print(max(0, -(-x // k)-1))
elif h == 1:
    x = sum([s[0][i] == '1' for i in range(w)])
    print(max(0, -(-x // k)-1))
else:
    print(ans)
### BUGGY CODE ###

n,m,s = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    G[u].append([v, a, b])
    G[v].append([u, a, b])
cd = [list(map(int, input().split())) for i in range(n)]

from heapq import heappop, heappush
max_money = n*60
state = [[float("inf")]*(max_money+1) for i in range(n)]
s = min(s, max_money)
heap = [(0,(0,s),1)]

while heap:
    time, (cur, money), flag = heappop(heap)
    if state[cur][money] <= time:
        continue
    state[cur][money] = time
    if flag:
        n_money = money
        n_time = time
        f = False
        for i in range(10000):
            n_money += cd[cur][0]
            n_time += cd[cur][1]
            if n_money > max_money:
                n_money = max_money
                f = True
            if state[cur][n_money] < n_time:
                break
            heappush(heap, (n_time, (cur, n_money), 0))
            if f:
                break
    for to, a,b in G[cur]:
        if money < a or state[to][money-a] <= time+b:
            continue
        heappush(heap, (time+b, (to, money-a), 1))

for i in range(1, n):
    print(min(state[i]))

### FIXED CODE ###

max_s = 2500

n,m,s = map(int, input().split())
s = min(s, max_s)
conv = lambda i,j : i*10000+j

G = [[] for i in range(conv(n-1, max_s)+1)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    for j in range(max_s+1):
        if j-a >= 0:
            G[conv(u,j)].append((conv(v,j-a), b))
            G[conv(v,j)].append((conv(u,j-a), b))

for i in range(n):
    c,d = map(int, input().split())
    for j in range(max_s+1):
        if j+c > max_s:
            break
        G[conv(i,j)].append((conv(i,j+c), d))

from heapq import heappush, heappop
def dijkstra(G, start):
    n = len(G)
    dist = [float("inf")]*n
    visited = set()
    heap = [(0, start)]

    while heap and len(visited) != n:
        d, cur = heappop(heap)
        if cur in visited:
            continue
        visited.add(cur)
        dist[cur] = d
        for to, cost in G[cur]:
            if to not in visited:
                heappush(heap, (d+cost, to))
    return dist

dist = dijkstra(G, conv(0, s))
for i in range(1,n):
    cost = min(dist[conv(i,0):conv(i,max_s)+1])
    print(cost)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0,abs(a[0]-a[1])]
co=0
for i in range(2,n):
 if(len(dp)<k+1):
  f=float('inf')
  for j in range(0,len(dp)):
   f=min(f,dp[j]+abs(a[i]-a[j]))
  dp.append(f)
 else:
  co+=1
  f=float('inf')
  for j in range(co,k+co):
   f=min(f,dp[j]+abs(a[i]-a[j]))
  dp.append(f)
print(dp[-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
def fun(n,a,k):
 dp=[0]*n
 for i in range(1,n):
  dp[i]=min([dp[j]+abs(a[i]-a[j]) for j in range(max(0,i-k),i)])
 print(dp[len(dp)-1])
if __name__ == '__main__':
 n,k = map(int, input().split())
 a=list(map(int,input().split()))
 fun(n,a,k)
### BUGGY CODE ###

n = int(input())
ans = sum(range(1, n))
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
if n %2 ==0:
  ans = (n-1) * (n//2)
else:
  ans = n * (n//2)
print(ans)
### BUGGY CODE ###

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

n = int(input())
cost = [10**10]*n
edge = [dict() for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    edge[a-1].update({b-1: c})
    edge[b-1].update({a-1: c})

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


def dfs(i, prev, d):
    cost[i] = d
    for j in edge[i].keys():
        if j == prev:
            continue
        dfs(j, i, d+edge[i][j])


dfs(K-1, -1, 0)

for _ in range(Q):
    x, y = map(int, input().split())
    print(cost[x-1]+cost[y-1])

### FIXED CODE ###

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

n = int(input())
cost = [10**10]*n
edge = [dict() for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    edge[a-1].update({b-1: c})
    edge[b-1].update({a-1: c})

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


def dfs(i, prev, d):
    cost[i] = d
    for j in edge[i].keys():
        if j == prev:
            continue
        dfs(j, i, d+edge[i][j])


dfs(K-1, -1, 0)

for _ in range(Q):
    x, y = map(int, input().split())
    print(cost[x-1]+cost[y-1])
### BUGGY CODE ###

def main():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    S = tuple(map(int, input().split()))
    T = tuple(map(int, input().split()))
    l = [[0] * (M + 1) for _ in range(N + 1)]
    l[0] = [1] * (M + 1)
    for i in range(N + 1):
        l[i][0] = 1
    r = 1
    for i in range(1, N+1):
        for j in range(1, M+1):
            if S[i-1] == T[j-1]:
                r += l[i-1][j-1]
                l[i][j] = l[i][j-1] + l[i-1][j]
            else:
                l[i][j] = l[i][j-1] + l[i-1][j] - l[i-1][j-1]
    print(r % MOD)
main()


### FIXED CODE ###

def main():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    S = tuple(map(int, input().split()))
    T = tuple(map(int, input().split()))
    l = [[0] * (M + 1) for _ in range(N + 1)]
    l[0] = [1] * (M + 1)
    for i in range(N + 1):
        l[i][0] = 1
    r = 1
    for i in range(1, N+1):
        for j in range(1, M+1):
            if S[i-1] == T[j-1]:
                r += l[i-1][j-1]
                l[i][j] = l[i][j-1] + l[i-1][j]
                l[i][j] %= MOD
            else:
                l[i][j] = l[i][j-1] + l[i-1][j] - l[i-1][j-1]
        r %= MOD
    print(r % MOD)
main()
### BUGGY CODE ###

monster, hisatu = map(int, input().split())
m_life = list(map(int, input().split()))
count = 0
if hisatu >= len(m_life):
    print(0)
else:
    while hisatu > 0:
        m_life.remove(max(m_life))
        hisatu -= 1
    for i in m_life:
        count += i
    print(count)

### FIXED CODE ###

monster, hisatu = map(int, input().split())
m_life = list(map(int, input().split()))
m_life.sort()
count = 0
for i in range(len(m_life)-hisatu):
    count += m_life[i]
print(count)
### BUGGY CODE ###

from collections import deque
S = input()
ans = deque(S)
Q = int(input())
for i in range(Q):
    a_list = input().split()
    if a_list[0] == "1":
        ans.reverse()
    elif a_list[1] == "1":
        ans.appendleft(a_list[2])
    else:
        ans.append(a_list[2])
ans = "".join(ans)
print(ans)

### FIXED CODE ###

from collections import deque
S = input()
ans = deque(S)
Q = int(input())
rev = False
for i in range(Q):
    a_list = input().split()
    if a_list[0] == "1":
        if rev == True:
            rev = False
        else:
            rev = True
    elif (a_list[1] == "1" and rev == False) or (a_list[1] == "2" and rev == True):
        ans.appendleft(a_list[2])
    else:
        ans.append(a_list[2])
if rev:
    ans.reverse()
ans = "".join(ans)
print(ans)
### BUGGY CODE ###

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

for i in range(n):
  print(a.index(i+1)+1)


### FIXED CODE ###

import numpy as np
n=int(input())
a=list(map(int,input().split()))
  
x = np.argsort(a)
for i in range(n):
  print(x[i]+1)
### BUGGY CODE ###

import sys
import math
import queue
import copy
import bisect#2分探索
from collections import deque #popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

S = int(input())
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

ss=str(S)
#print(ss)
ls=len(ss)
l=[0]*(ls+1)
for i in range(0,ls):
    l[i]=int(ss[i:ls])%2019
    #print(l[i])
#print(l)
l.sort()
#print(l)

cur=-1
ans=0
for i, li in enumerate(l):
    if cur==-1:
        cur=li
        count=1
    elif li==cur:
        count+=1
    else:
        ans+=count*(count-1)//2
        cur=li
        count=1

print(ans)

### FIXED CODE ###

import sys
import math
import queue
import copy
import bisect#2分探索
from collections import deque #popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

ss = input()
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

#ss=str(S)
# #print(ss)
ls=len(ss)
# l=[0]*(ls+1)

    #print(l[i])
#print(l)

# #優先度付きqueue

kl=[0]*2019
kl[0]=1
# a = [0]
# heapq.heapify(a)  # aを優先度付きキューに

tmp=0
t2=1
for s in reversed(ss):
    tmp=(tmp+int(s)*t2)%2019
    kl[tmp]+=1
    t2=t2*10%2019
    #print(tmp)

#print(a)




ans=0
for k in kl:
    ans+=k*(k-1)//2
print(ans)

# cur=-1
# ans=0
# for i, li in enumerate(l):
#     if cur==-1:
#         cur=li
#         count=1
#     elif li==cur:
#         count+=1
#     else:
#         ans+=count*(count-1)//2
#         cur=li
#         count=1

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

###### Importing Libraries ######
import math
import operator as op
from functools import reduce
from fractions import Fraction as frac
#################################
##### User defined function #####

############ NCR ###############
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
    
############ READ ###############
def rd(p):
    if(p==0):
        return input()
    if(p==1):
        return int(input())
    if(p==2):
        return map(int,input().split())
    if(p==3):
        return list(map(int,input().split()))


############ DSU ###############
global par
# par=[-1 for i in range(100001)]
# t=rd(1)
def find(u):
    if(par[u]<0):
        return u
    else:
        return find(par[u])
def uni(x,y):
    u=find(x)
    v=find(y)
    if u==v:
        return
    if(par[u]<par[v]):
        par[u]+=par[v]
        par[v]=u
    else:    
        par[v]+=par[u]
        par[u]=v
################################        
        

t=1
for term in range(1,t+1):
    h,n=rd(2)
    P=[rd(3) for i in range(n)]
    x=max(a for a,b in P)
    DP=[0 for i in range(h+x)]
    for i in range(1,h+x):
        DP[i]=min(DP[max(i-a,0)]+b for a,b in P)
    print(DP[h])
    
    
    
    
    
    
    
    
    
    
    
    

### FIXED CODE ###

###### Importing Libraries ######
import math
import operator as op
from functools import reduce
from fractions import Fraction as frac
#################################
##### User defined function #####

############ NCR ###############
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
    
############ READ ###############
def rd(p):
    if(p==0):
        return input()
    if(p==1):
        return int(input())
    if(p==2):
        return map(int,input().split())
    if(p==3):
        return list(map(int,input().split()))


############ DSU ###############
global par
# par=[-1 for i in range(100001)]
# t=rd(1)
def find(u):
    if(par[u]<0):
        return u
    else:
        return find(par[u])
def uni(x,y):
    u=find(x)
    v=find(y)
    if u==v:
        return
    if(par[u]<par[v]):
        par[u]+=par[v]
        par[v]=u
    else:    
        par[v]+=par[u]
        par[u]=v
################################        
        

t=1
for term in range(1,t+1):
    h,n=rd(2)
    P=[list(map(int,input().split())) for i in range(n)]
    x=max(a for a,b in P)
    DP=[0]*(h+x)
    for i in range(1,h+x):
        DP[i]=min(DP[i-a]+b for a,b in P)
    print(DP[h])