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

n = int(input())
lst = [[-1]*n for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int, input().split())
        lst[i][x-1] = y

item = [i for i in range(2**n)]
def bitka(n):
    honest = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            honest.append(item[j])  # フラグが立っていたら bag に果物を詰める
    return honest

def check(honest, lst):
    for i in honest:
        for j in range(n):
            if lst[i][j]==1:
                if j not in honest:
                    return False
            elif lst[i][j]==0:
                if j in honest:
                    return False
    return True

ans = 0
for i in range(2**n):
    if check(bitka(i),lst)==True:
        ans = max(ans, len(bitka(i)))
print(ans)


### FIXED CODE ###

n = int(input())
ms = []
say = []
for i in range(n):
    m = int(input())
    ms.append(m)
    say.append([])
    for j in range(m):
        p,q = list(map(int, input().split()))
        say[i].append([p,q])

# ms =  [2, 2, 2]
# say = [[[2, 1], [3, 0]], [[3, 1], [1, 0]], [[1, 1], [2, 0]]]

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

ans = 0
for i in range(2**n):
    flag = 1
    nowbit = bitlist(i,n)
    for j in range(n):
        for k in range(ms[j]):
            if nowbit[j]==1:
                if say[j][k][1] != nowbit[say[j][k][0]-1]:
                    flag = 0
    if flag == 1:
        ans = max(ans, sum(nowbit))

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

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

mod = 10**9+7

mm0 = [0 for i in range(61)]
mm1 = [0 for i in range(61)]

for i in range(n):
    for j in range(61):
        if (a[i]>>j)<0:
            break
        if (a[i]>>j)&1:
            mm1[j] += 1

for i in range(61):
    mm0[i] = n-mm1[i] 

ans = 0

for i in range(61):
    ttl = mm0[i]*mm1[i]
    ans += ((1<<i)*ttl)%mod
    ans %= mod

print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
 
mod = 10**9+7
 
 
 
ans = 0
q2 = 1
for j in range(60):
    mm1 = 0
    for i in range(n):
        if a[i]>>j&1:
            mm1 += 1
 
    ttl = ((n-mm1)*mm1)
    ans += ((q2)*((ttl)%mod))%mod
    ans %= mod
    q2 = (q2*2)%mod
 
print(ans)
### BUGGY CODE ###

mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(60):
    cnt = 0
    for j in range(N):
        cnt += (A[j]>>i)&1
    ans = (ans+(N-cnt)*cnt*2**i)%mod
print(ans)



### FIXED CODE ###

mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(60):
    cnt = 0
    for j in range(N):
        cnt += (A[j]>>i)&1
    ans = (ans+(((N-cnt)*cnt)%mod)*2**i)%mod
print(ans)
### BUGGY CODE ###

s = input()
if len(s) <= 3:
  print(0)
  exit()

chk = [str((i+1)*2019) for i in range(1000)]
ans = 0
for i in chk:
  for j in range(len(s)-len(i)+1):
    ans += s.count(i,j,j+len(i))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = input().strip()
if len(s) <= 3:
  print(0)
  exit()
c = 0
chk = [0]*2019
for i,si in enumerate(s[::-1]):
  c += int(si)*pow(10,i,2019)
  chk[c%2019] += 1
ans = chk[0]
for i in chk:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

from bisect import *
P=998244353
N,K=map(int,input().split())
LR=[]
for _ in range(K):
  l,r=map(int,input().split())
  LR+=range(l,r+1)
LR=list(set(LR))
c=[0]*N
c[0]=1
for k in range(N):
  S=LR[:]
  while len(S):
    if S[-1]>k:
      S.pop()
      continue
    c[k]+=c[k-S[-1]]%P
    S.pop()
print(c[-1]%P)

### FIXED CODE ###

P=998244353
N,K=map(int, input().split())
LR=[list(map(int, input().split())) for _ in range(K)]

s=[0 for _ in range(N+1)]
s[1]=1
for i in range(1,N):
  s[i+1] = s[i]
  for l,r in LR:
    s[i+1]+=(s[max(0,i-l+1)]-s[max(0,i-r)])%P
    s[i+1]%=P
print((s[N]-s[N-1])%P)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]
res = [0]*4
ans = 10**18
data = res[:]
s = 0
t = 2
for i in range(1, n - 1):
    for j in range(s, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        for k in range(t, n-1):
            res[2] = F[k] - F[i]
            res[3] = F[n - 1] - F[k]
            if ans > max(res) - min(res):
                s = j
                t = k
                data = res[:]
                ans = min(ans, max(res) - min(res))
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]


res = [0]*4
data = [10 ** 18] * 2
ex = [0]*4
ans = 10 ** 18
s = 0
t = 2
for i in range(1, n - 2):
    bl = [True, True]
    for j in range(s, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        if not bl[0]:
            break
        if data[0] > abs(res[1] - res[0]) or j == s:
            s = j
            ex[0] = res[0]
            ex[1] = res[1]
            data[0] = abs(res[1] - res[0])
        else:
            bl[0] = False
    for k in range(t, n):
        res[2] = F[k] - F[i]
        res[3] = F[n - 1] - F[k]
        if not bl[1]:
            break
        if data[1] > abs(res[3] - res[2]) or k == t:
            t = k
            ex[2] = res[2]
            ex[3] = res[3]
            data[1] = abs(res[3] - res[2])
        else:
            bl[1] = False
    ans = min(ans, max(ex) - min(ex))

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

import sys
import numpy as np

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, K = map(int, readline().split())
    np.set_printoptions(precision=0)
    A = np.array(readline().split(), np.int64)
    for _ in range(K):
        B = np.zeros(N + 1)
        for i, a in enumerate(A):
            B[max(0, int(i - a))] += 1
            B[min(int(i + a + 1), N)] -= 1
        B = B.cumsum()
        A = np.copy(B[:N])
    print(' '.join(map(str, list(map(int, A)))))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


@njit('i8[:](i8,i8,i8[:])', cache=True)
def func(n, k, A):
    for _ in range(k):
        B = np.zeros(n + 1, np.int64)
        for i, a in enumerate(A):
            B[max(0, i - a)] += 1
            B[min(i + a + 1, n)] -= 1
        A = B.cumsum()[:-1]
        if np.all(A == n):
            break
    return A


def main():
    N, K = map(int, readline().split())
    A = np.array(readline().split(), np.int64)
    ans = func(N, K, A)
    print(*ans)


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

#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]"):
    if 1 not in a:
        print(-1)
        return
    ans = 0
    for i in range(1, N):
        try:
            idx = len(a) - 1 - a[::-1].index(i)
            a = a[idx:]
            ans += idx if i == 1 else idx - 1
        except Exception:
            ans += len(a) - 1
            break
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]"):
    if 1 not in a:
        print(-1)
        return
    ans = 0
    nxt = 1
    for i in range(N):
        if a[i] == nxt:
            nxt += 1
        else:
            ans += 1
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


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

def LCM(m,n):
  for i in range(1,m+1)[::-1]:
    if n%i==0:
      return i
    
N,X=(int(i) for i in input().split(' '))
x=[int(i) for i in input().split(' ')]
x=[X]+x
x.sort()
D=x[1]-x[0]
for i in range(N):
  D=LCM(D,x[i+1]-x[i])
print(D)

### FIXED CODE ###

def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    # データの状態に左右されないためにrandom.choice()を用いることもある。
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right

def LCM(m,n):
  if m>n:
    m,n=n,m
  for i in range(1,m+1)[::-1]:
    if n%i==0:
      return i
    
N,X=(int(i) for i in input().split(' '))
x=[int(i) for i in input().split(' ')]
x=[X]+x
x=quick_sort(x)
D=abs(x[1]-x[0])
for i in range(N):
  D=LCM(D,abs(x[i+1]-x[i]))
print(D)
### BUGGY CODE ###

X = int(input())

i = 0
while True:
  tmp = X - i**5
  if abs(tmp**0.2 - int(tmp**0.2)) < 1e-8:
    print("{} {}".format(i, int(tmp**0.2)))
   
  if abs(tmp**0.2 - int(-tmp**0.2)) < 1e-8:
    print("{} {}".format(i, int(-tmp**0.2)))

### FIXED CODE ###

def main():
    X = int(input())

    a = -1
    
    while True:
        b1 = 0
        b2 = 0
        while b1 < a:
            
            if (X/(a-b1)).is_integer():
                if int(X/(a-b1)) == a**4 + b1*(a**3) + (a**2)*(b1**2) + a*(b1**3) + b1**4:
                    print("{} {}\n".format(a, b1))
                    return 0

            if (X/(a-b2)).is_integer():
                if int(X/(a-b2)) == a**4 + b2*(a**3) + (a**2)*(b2**2) + a*(b2**3) + b2**4:
                    print("{} {}\n".format(a, b2))
                    return 0

            b1 += 1
            b2 -= 1
            
        a += 1


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

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

X = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((i, x, y))

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

X = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((i, x, y))

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))
### BUGGY CODE ###

n = int(input())
s = input()
ans = []
for i in range(0,n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      a = s[i]+s[j]+s[k]
      ans.append(a)
ans = set(ans)
print(len(ans))


### FIXED CODE ###

n = int(input())
s = input()
lst = [0] * 1000
for i in range(1000):
    if len(str(i)) == 1:
        tmp = '00' + str(i)
        lst[i] = tmp
    elif len(str(i)) == 2:
        tmp = '0' + str(i)
        lst[i] = tmp
    else:
        lst[i] = str(i)

cnt = 0
for v in lst:
    id_1 = s.find(v[0])
    if id_1 == -1:
        continue
    id_2 = s.find(v[1], id_1 + 1)
    if id_2 == -1:
        continue
    id_3 = s.find(v[2], id_2 + 1)
    if id_3 == -1:
        continue
    cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
  a = [str(i//100), str((i//10)%10), str(i%10)]
  cnt = 0
  for j in range(n):
    if cnt <= 2 and a[cnt] == s[j]: cnt+=1
  if cnt == 3: ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
  a = [i//100, (i//10)%10, i%10]
  cnt = 0
  for j in range(n):
    if cnt <= 2 and a[cnt] == int(s[j]): cnt+=1
  if cnt == 3: ans += 1
print(ans)
### BUGGY CODE ###

s = str(input())
t = str(input())

ls = list(s)
lt = list(t)

ans = 0
while True:
  rep_cnt = 0
  j = 0
  for i in range(j, len(ls)):
    j += 1
    if ls[i] != lt[i]:
      ls[i] = lt[i]
      rep_cnt += 1
      break
  if rep_cnt > 0:
    ans += rep_cnt
  else:
    break

print(str(ans))



### FIXED CODE ###

s = str(input())
t = str(input())

ls = list(s)
lt = list(t)

ans = 0
j = 0
while True:
  rep_cnt = 0
  for i in range(j, len(ls)):
    j += 1
    if ls[i] != lt[i]:
      ls[i] = lt[i]
      rep_cnt += 1
      break
  if rep_cnt > 0:
    ans += rep_cnt
  else:
    break

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

from itertools import combinations
from collections import deque

N = int(input())
S = input()

idxs = [i for i in range(N)]

ans = 0
for i in range(N):
    for j in range(i, N):
        for k in range(j, N):
            if j - i != k - j:
                if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                    ans += 1


"""
data = deque()
for c in combinations(idxs, 3):
    i, j, k = c
    if j-i != k-j:
        data.append(c)

ans = 0
for c in data:
    # i, j, k = sorted(c)
    i, j, k = c
    s0 = S[i]
    s1 = S[j]
    s2 = S[k]

    if s0 != s1 and s1 != s2 and s0 != s2:
        ans += 1
"""

print(ans)


### FIXED CODE ###


N = int(input())
S = input()

ris = [i for i, s in enumerate(S) if s == "R"]
gis = [i for i, s in enumerate(S) if s == "G"]
bis = [i for i, s in enumerate(S) if s == "B"]

all = len(ris) * len(gis) * len(bis)

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        k = 2*j - i
        if 0 <= k < N:
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                cnt += 1

ans = all - cnt


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

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, K, C = lr()
    S = [i for i, s in enumerate(sr()) if s == 'o']
    ans = []
    for i in S:
        no_work = -1
        cnt = 0
        for j in S:
            if j == i:
                continue
            if j <= no_work:
                continue
            cnt += 1
            no_work = j+C
        if cnt < K:
            ans.append(i+1)
    print(*ans, sep='\n')
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import Counter
def resolve():
    N, K, C = lr()
    S = [i+1 for i, s in enumerate(sr()) if s == 'o']
    l = [S[0]]
    for i in S[1:]:
        if l[-1]+C >= i or len(l) > K:
            continue
        l.append(i)
    S = S[::-1]
    r = [S[0]]
    for i in S[1:]:
        if r[-1]-C <= i or len(r) > K:
            continue
        r.append(i)
    r = r[::-1]
    for i in range(K):
        if l[i] == r[i]:
            print(l[i])
resolve()
### BUGGY CODE ###

import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        break
Q = collections.deque([[i, j, 0]])
hmin = hmax = i
wmin = wmax = j
while Q:
    h, w, dist = Q.popleft()
    A[h][w] = '#'
    hmin = min(hmin, h)
    hmax = max(hmax, h)
    wmin = min(wmin, w)
    wmax = max(wmax, w)
    if dist < K:
        for nh, nw in [[h - 1, w], [h + 1, w], [h, w - 1], [h, w + 1]]:
            if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                Q += [[nh, nw, dist + 1]]
print(1 +
      min([math.ceil(_ / K)
           for _ in (hmin, H - 1 - hmax, wmin, W - 1 - wmax)]))


### FIXED CODE ###

import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for h in range(H):
    if 'S' in A[h]:
        w = A[h].index('S')
        break
visited = [[False] * W for _ in range(H)]
ans = min([h, H - 1 - h, w, W - 1 - w])
res = K - 1
Q = collections.deque([[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                       [h, w + 1, res]])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.' and not visited[h][w]:
        visited[h][w] = True
        ans = min([ans, h, H - 1 - h, w, W - 1 - w])
        if res:
            res -= 1
            Q += [[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                  [h, w + 1, res]]
print(1 + math.ceil(ans / K))
### BUGGY CODE ###

x,y = map(int,input().split())
p = list(map(int,input().split()))

bigNumber = 0

for i in range(x-y+1):

    number = sum(p[i:i+y])

    if number > bigNumber:
        bigNumber = number

print((bigNumber + y) / 2)



### FIXED CODE ###

def main():
    x,y = map(int,input().split())
    p = list(map(int,input().split()))

    number = sum(p[0:y])
    bigNumber = number

    for i in range(x-y):

        number = number - p[i] + p[i+y]

        if number > bigNumber:
            bigNumber = number

    print((bigNumber + y) / 2)

main()
### BUGGY CODE ###

s = list(input())
ans = [0 for _ in range(len(s))]
for i in range(len(s)):
    location = i
    flag = [0, 0]
    counter = 0
    while(1):
        if s[location] == 'R':
            location += 1
            counter += 1
            flag[1] = 1
        else:
            location -= 1
            counter += 1
            flag[0] = 1
        if flag[0]+flag[1] == 2:
            # ループの処理
            if counter%2 == 0:
                ans[location] += 1
            elif s[location] == 'R':
                ans[location+1] += 1
            else:
                ans[location-1] += 1
            break
print(' '.join(map(str, ans)))


### FIXED CODE ###

s = list(input())
ans = [0 for _ in range(len(s))]
# for i in range(len(s)):
#     location = i
#     flag = [0, 0]
#     counter = 0
#     while(1):
#         if s[location] == 'R':
#             location += 1
#             counter += 1
#             flag[1] = 1
#         else:
#             location -= 1
#             counter += 1
#             flag[0] = 1
#         if flag[0]+flag[1] == 2:
#             # ループの処理
#             if counter%2 == 0:
#                 ans[location] += 1
#             elif s[location] == 'R':
#                 ans[location+1] += 1
#             else:
#                 ans[location-1] += 1
#             break
counter = 0
index = 0
is_R = True
l_index = 0
while(index < len(s)):
    # Rが続く場合
    if is_R:
        if s[index] == 'R':
            counter += 1
            index += 1
        else:
            l_index = index
            ans[l_index] += (counter)//2
            ans[l_index-1] += (counter-1)//2+1
            # print('L',l_index, counter, ans)
            counter = 1
            is_R = False
            index += 1
    else:
        if s[index] == 'L':
            counter += 1
            index += 1
        else:
            ans[l_index] += (counter-1)//2+1
            ans[l_index-1] += (counter)//2
            l_index = index-1
            # print('R',l_index, counter, ans)
            counter = 1
            is_R = True
            index += 1
ans[l_index] += (counter-1)//2+1
ans[l_index-1] += (counter)//2
# print(l_index, counter, ans)
print(' '.join(map(str, ans)))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
lists=list(map(int,input().split()))
aa=[0 for i in range(n)]
bb=[0 for i in range(n)]
length=61
use=[0 for i in range(61)]
for  j in range(n):
    k=format(lists[j],"0%ib"%length)
    k=k[::-1]
    aa[j]=k[:30]  
    bb[j]=k[30:]
for p in aa:    
    for some in range(30):
        use[some]+=int(p[some])
for q in bb:    
    for some in range(31):
        use[some+30]+=int(q[some])
answer=0

for j in range(61):
    answer+=(2**j)*use[j]*(n-use[j])%(10**9+7)
print(answer%(10**9+7))

### FIXED CODE ###

n=int(input())
lists=list(map(int,input().split()))
length=61
use=[0 for i in range(61)]
a,b=divmod(n,9)
anslist=[0 for i in range(a+1)]
for  j in range(n):
    k=format(lists[j],"0%ib"%length)
    k=k[::-1]
    p,q=divmod(j,9)
    if p>a:
        anslist.append(str(k))
    else:
        anslist[p]+=int(k)
answer=0
for some in anslist:
    some=str(some)
    some=some.zfill(61)
    for j in range(61):
        if int(some[j])!=0:
            use[j]+=int(some[j])

for j in range(61):
    answer+=(2**j)*use[j]*(n-use[j])%(10**9+7)
print(answer%(10**9+7))
### BUGGY CODE ###

n = int(input())
l = [int(i) for i in input().split()]
l.sort(reverse=True)
ans = 0
for i in range(n-2):
  c = l[i]
  for j in range(i+1, n-1):
    b = l[j]
    k_max = n-1
    k_min = j
    while k_min<k_max:
      k = (k_max+k_min)//2+1
      a = l[k]
      if c < a + b:
        k_min = k
      else:
        k_max = k-1
    ans += k_min - j
print(ans)


### FIXED CODE ###

from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    ans += bisect_left(l, l[i]+l[j]) - j - 1
print(ans)
### BUGGY CODE ###

h, n = map(int, input().split())
INF = 10 ** 9
dp = [INF for _ in range(2*10**4)]
AB = [tuple(map(int, input().split())) for _ in range(n)]
dp[0] = 0
for a, b in AB:
    for i in range(h):
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))

### FIXED CODE ###

def main():
    h, n = map(int, input().split())
    INF = 10 ** 9
    dp = [INF for _ in range(2*10**4)]
    AB = [tuple(map(int, input().split())) for _ in range(n)]
    dp[0] = 0
    for a, b in AB:
        for i in range(h):
            dp[i + a] = min(dp[i + a], dp[i] + b)
    print(min(dp[h:]))
if __name__ == "__main__":
    main()