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

n = int(input())

l = []
cnt = 0
t = 0
tmp = '0000000000'

for i in range(n):
    s = str(input())
    sl = ''.join(sorted(s))
    l.append(sl)
    l.sort()

for i in range(n):
  if tmp == l[i]:
    cnt += 1
  else:
    tmp = l[i]
    if cnt > 0:
      t += int(cnt * (cnt + 1) / 2)
    cnt = 0
else:
  if cnt > 0:
    t += int(cnt * (cnt + 1) / 2)
    
print(t)

### FIXED CODE ###

n = int(input())

l = []
cnt = 0
t = 0

for i in range(n):
    s = str(input())
    sl = ''.join(sorted(s))
    l.append(sl)

l.sort()

tmp = l[0]

for i in range(1, n):
  if tmp == l[i]:
    cnt += 1
  else:
    tmp = l[i]
    t += int(cnt * (cnt + 1) / 2)
    cnt = 0
else:
    t += int(cnt * (cnt + 1) / 2)

print(t)
### BUGGY CODE ###

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

b = []
for i in range(n):
    b.append(a[i])
    b = b[::-1]
print(' '.join(map(str, b)))

### FIXED CODE ###

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

b = []
if n % 2 == 0:
    for i in range(n//2):
        b.append(a[-1-i*2])
    for i in range(n//2):
        b.append(a[i*2])
else:
    for i in range(n//2+1):
        b.append(a[-1-i*2])
    for i in range(0, n//2):
        b.append(a[1+i*2])
print(' '.join(map(str, b)))
### BUGGY CODE ###

def solve():
    ans = 1
    N = int(input())
    s = input()
    ans = 0
    for i in range(1000):
        t = str(i).zfill(3)
        t_index = 0 
        for s_index in range(N):
            if s[s_index] == t[t_index]:
                t_index += 1
                if t_index == 3:
                    break
        if t_index == 3:
            ans += 1
    print(ans)
solve()

### FIXED CODE ###

n = int(input())
a = input()

r = 0
for i in range(10):
  s = a.find(str(i))
  if s == -1:
    continue
  for j in range(10):
    s2 = a.find(str(j), s + 1)
    if s2 == -1:
      continue
    for k in range(10):
      if a.find(str(k), s2 + 1) != -1:
        r += 1
print(r)
### BUGGY CODE ###

n,k = map(int,input().split())
h = [int(i) for i in input().split()]
dp = [float("inf")]*n
dp[0] = 0
for i in range(1,n):
    dp[i] = min(dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i))
print(dp[-1])

### FIXED CODE ###

def solve():
  n,k = map(int,input().split())
  h = list(map(int,input().split()))
  dp = [float("inf")]*n
  dp[0] = 0
  for i in range(0,n-1):
    for j in range(1,k+1):
      if (i-j)>=-1:
        dp[i+1]=min(dp[i+1],dp[i+1-j]+abs(h[i+1]-h[i+1-j]))
  print(dp[-1])
solve()
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
stand_bit = [set() for i in range(64)]
acc = [0 for i in range(n+1)]
acc[0] = 0
for i in range(1, n+1):
    acc[i] += a[i-1] + acc[i-1]
set_ans = set()
for i in range(n):
    for j in range(i, n):
        set_ans.add(acc[j+1] - acc[i])
        s = "{:b}".format(acc[j+1] - acc[i])
        s = s.zfill(64)
        for num, bit in enumerate(s):
            if bit == "1":
                stand_bit[num].add(acc[j+1] - acc[i])
for i in range(64):
    if len(set_ans & stand_bit[i]) >= k:
        set_ans &= stand_bit[i]
ans_list = list(set_ans)
ans = ans_list[0]
for i in ans_list:
    ans &= i
print(ans)



### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
stand_bit = [set() for i in range(42)]
acc = [0 for i in range(n+1)]
for i in range(1, n+1):
    acc[i] += a[i-1] + acc[i-1]
set_ans = set()
for i in range(n):
    for j in range(i, n):
        tmp = acc[j+1] - acc[i]
        set_ans.add(tmp)
        s = tmp
        index = 41
        while s:
            if s & 1:
                stand_bit[index].add(tmp)
            s = s >> 1
            index -= 1
for i in range(42):
    if len(set_ans & stand_bit[i]) >= k:
        set_ans &= stand_bit[i]
ans_list = list(set_ans)
ans = ans_list[0]
for i in ans_list:
    ans &= i
print(ans)
### BUGGY CODE ###

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

L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]

for i in range(h):
    cnt_L = 1
    for j in range(w):
        if (lst[i][j] == '#'):
            cnt_L =1
        else:
            L[i][j] = cnt_L
            cnt_L += 1
            
    cnt_R = 1
    for k in range(w)[::-1]:
        if (lst[i][k] == '#'):
            cnt_R = 1
        else:
            R[i][k] = cnt_R
            cnt_R += 1

for i in range(w):
    cnt_U = 1
    for j in range(h):
        if (lst[j][i] == '#'):
            cnt_U = 1
        else:
            U[j][i] = cnt_U
            cnt_U += 1
    
    cnt_D = 1
    for k in range(h)[::-1]:
        if (lst[k][i] == '#'):
            cnt_D = 1
        else:
            D[k][i] = cnt_D
            cnt_D += 1

ans = 0
for i in range(h):
    for j in range(w):
        tmp = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
        if tmp > ans:
            ans = tmp
print(ans)

### FIXED CODE ###

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

L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]

for i in range(h):
    cnt_L = 1
    for j in range(w):
        if (lst[i][j] == '#'):
            cnt_L =1
        else:
            L[i][j] = cnt_L
            cnt_L += 1
            
    cnt_R = 1
    for k in range(w)[::-1]:
        if (lst[i][k] == '#'):
            cnt_R = 1
        else:
            R[i][k] = cnt_R
            cnt_R += 1

for i in range(w):
    cnt_U = 1
    for j in range(h):
        if (lst[j][i] == '#'):
            cnt_U = 1
        else:
            U[j][i] = cnt_U
            cnt_U += 1
    
    cnt_D = 1
    for k in range(h)[::-1]:
        if (lst[k][i] == '#'):
            cnt_D = 1
        else:
            D[k][i] = cnt_D
            cnt_D += 1

ans = 0
for i in range(h):
    for j in range(w):
        tmp = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
        if tmp > ans:
            ans = tmp
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
ans=1
for i in range(k):
    ans=l[i]*ans

for i in range(k,n):
    prevans=ans
    ans=(ans*l[i])//l[i-k]
    if ans>prevans:
        print("Yes")
    else:
        print("No")




### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
ans=1
for i in range(k):
    ans=l[i]

for i in range(k,n):
    prevans=l[i-k]
    ans=l[i]
    if ans>prevans:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

def road_find(a):
    if Road[a] < 0:
        return a
    else:
        return road_find(Road[a])


def train_find(a):
    if Train[a] < 0:
        return a
    else:
        return train_find(Train[a])


def road_union(a, b):
    ag = road_find(a)
    bg = road_find(b)
    if ag == bg:
        return
    if Road[ag] > Road[bg]:
        ag, bg = bg, ag
    Road[ag] += Road[bg]
    Road[bg] = ag
    return


def train_union(a, b):
    ag = train_find(a)
    bg = train_find(b)
    if ag == bg:
        return
    if Train[ag] > Train[bg]:
        ag, bg = bg, ag
    Train[ag] += Train[bg]
    Train[bg] = ag
    return


N, K, L = map(int, input().split())
Road = [-1] * N
Train = [-1] * N
RoadG = [[] for _ in range(N)]
TrainG = [[] for _ in range(N)]

for road in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    road_union(p, q)
for i in range(N):
    RoadG[road_find(i)].append(i)

for train in range(L):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    train_union(p, q)
for i in range(N):
    TrainG[train_find(i)].append(i)


for i in range(N):
    i_road_g = road_find(i)
    i_train_g = train_find(i)
    print(len(set(TrainG[i_train_g]) & set(RoadG[i_road_g])), end=' ')


### FIXED CODE ###

from collections import Counter

def road_find(a):
    if Road[a] < 0:
        return a
    else:
        return road_find(Road[a])


def train_find(a):
    if Train[a] < 0:
        return a
    else:
        return train_find(Train[a])


def road_union(a, b):
    ag = road_find(a)
    bg = road_find(b)
    if ag == bg:
        return
    if Road[ag] > Road[bg]:
        ag, bg = bg, ag
    Road[ag] += Road[bg]
    Road[bg] = ag
    return


def train_union(a, b):
    ag = train_find(a)
    bg = train_find(b)
    if ag == bg:
        return
    if Train[ag] > Train[bg]:
        ag, bg = bg, ag
    Train[ag] += Train[bg]
    Train[bg] = ag
    return


N, K, L = map(int, input().split())
Road = [-1] * N
Train = [-1] * N

for road in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    road_union(p, q)

for train in range(L):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    train_union(p, q)

Ans = []
for i in range(N):
    Ans.append((road_find(i),train_find(i)))

Ans_C = Counter(Ans)

for i in range(N):
    print(Ans_C[(road_find(i),train_find(i))])
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a= list(map(int, input().split()))
    a.sort()
    flag = [1]*(10**6+1)
    for i in range(n):
        if (flag[a[i]]==1):
            for j in range(2*a[i],10**6+1,a[i]):            
                flag[j] = 0
    x = collections.Counter(a)
    ans = 0
    for i in a:
        if (flag[i]==1):
            ans += 1
            flag[i]=0
            if (x[i]>1):
                ans -=1
    print(ans)

if __name__=="__main__":
    main()

### FIXED CODE ###

#import collections
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a= list(map(int, input().split()))
    a.sort()
    ans = 0
    flag = [1]*(10**6+1)
    for i in range(n):
        if (flag[a[i]]==0):
            continue
        tmp = a[i]
        while tmp < 10**6+1:
            flag[tmp] = False
            tmp += a[i]
        if i<n-1:
            if (a[i+1]==a[i]):
                continue
        ans += 1
    #x = collections.Counter(a)
    #ans = 0
    #for i in a:
        #if (flag[i]==1):
            #ans += 1
            #flag[i]=0
            #if (x[i]>1):
                #ans -=1
    print(ans)

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

N,M=(int(x) for x in input().split())
L=[]
D=[0]*M

for i in range(N):
    L.append(tuple(int(x) for x in input().split()))

L = sorted(L, key=lambda x:-x[1])
pay=0
for ab in L:
    if ab[0]<=M:
        for i in range(M-ab[0]+1):
            if D[M-ab[0]-i]==0:
                D[M-ab[0]-i]=1
                pay+=ab[1]
                break

print(pay)


### FIXED CODE ###

N,M=(int(x) for x in input().split())
L=[]
D=[0]*M

for i in range(N):
    L.append(tuple(int(x) for x in input().split()))

L = sorted(L, key=lambda x:-x[1])
pay=0
mn=-1
for ab in L:
    flag=True
    if ab[0]<=M and mn<M-ab[0]:
        i=0
        while True:
            if M-ab[0]-i<0:
                break
            if mn>M-ab[0]-i:
                break
            D[M-ab[0]-i]+=1
            if D[M-ab[0]-i]==1:
                pay+=ab[1]
                flag=False
                break
            else:
                if i==1:
                    i+=1
                else:
                    i+=D[M-ab[0]-i]-1
            
        if flag:
            mn=M-ab[0]
            
print(pay)
### BUGGY CODE ###

import collections

N = int(input())

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

c = collections.Counter(A)
# print(c)
dic = {}
for k,v in c.items():
    dic[k] = int(v*(v-1)/2)
# print(dic)

for k in range(N):
    Ak = A[k]
    ans = dic.copy()
    ans[Ak] = int((c[Ak]-1)*(c[Ak]-2)/2)
    # print(dic,ans)
    print(sum(ans.values()))

### FIXED CODE ###

import collections

N = int(input())

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

c = collections.Counter(A)
# print(c)
# dic = {}
ans = 0
# for k,v in c.items():
#     dic[k] = int(v*(v-1)/2)
# print(dic)
for v in c.values():
    ans += int(v*(v-1)/2)

for k in range(N):
    Ak = A[k]
    cAk = c[Ak]
    ansk = ans - cAk + 1
    # ans[Ak] = int((cAk-1)*(cAk-2)/2)
    # print(dic,ans)
    print(ansk)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [100000] * N

dp[0] = 0

for i in range(1,N):
    H = h[i]
    dp[i] = min( dp[j] + abs(h[j] - H) for j in range(max(0, i-K),i))


print(dp[N-1])

### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    H = h[i]
    dp[i] = min([dp[j] + abs(h[j] - H) for j in range(max(0, i - k), i)])
print(dp[-1])
### BUGGY CODE ###

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

def f(l, s, mn):
    ng = s - 1
    ok = len(l)
    while abs(ng - ok) > 1:
        i = (ok + ng) // 2
        x = l[i]
        if mn < x:
            ok = i
        else:
            ng = i
    return ok

ans = 0
bs = 0
for a in A:
    cs = 0
    bs = f(B, bs, a)
    for bi in range(bs, N):
        cs = f(C, cs, B[bi])
        ans += N - cs

print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()

ans = 0
for b in B:
    acnt = bisect_left(A, b)
    ccnt = N - bisect_right(C, b)
    ans += acnt * ccnt
print(ans)
### BUGGY CODE ###

from collections import deque

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

def merge(s, t):
    u = []

    while s + t:
        
        if s == [] or t == []:
            return u + s + t

        if s[0] <= t[0]:
            u.append(s[0])
            s = s[1:]
        else: # s0 > t0
            u.append(t[0])
            t = t[1:]

    return u

while len(A) > 1:
    B = []
    for i in range(len(A) // 2):
        B.append(merge(A[2 * i], A[2 * i + 1]))
    if len(A) % 2 == 1:
        B.append(A[len(A) - 1])
    A = B

A = A[0]
check = [True for _ in range(N)]

for i in range(N):
    if check[i] == True:
        a = A[i]
        for j in range(i + 1, N):
            if check[j] == True:
                if A[j] % a == 0:
                    check[j] = False
                    if j == i + 1:
                        if A[j] <= a:
                            check[i] = False

ans = check.count(True)
                            
print(ans)

### FIXED CODE ###

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

count = [0] * (M + 1)
for i in range(N):
    count[A[i]] += 1

check = [True] * (M + 1)
for a in range(1, M + 1):
    if count[a] > 0 and check[a] == True:
        for k in range(2, M // a + 1):
            check[a * k] = False      

ans = 0
for i in range(N):
    if count[A[i]] == 1 and check[A[i]] == True:
        ans += 1

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

n=int(input())
a=list(map(int,input().split()))
x=sum([(a.count(i)*(a.count(i)-1))//2 for i in set(a)])
for i in a:
  y=a.count(i)-1
  print(max(0,x-y))

### FIXED CODE ###

def main():
  from collections import Counter
  n=int(input())
  a,b=tuple(map(int,input().split())),[0]*n
  c=Counter(a)
  x=0
  for i in set(a):
    b[i-1]=c[i]
    x+=(b[i-1]*(b[i-1]-1))//2
  b=tuple(b)
  for i in a:
    y=b[i-1]-1
    print(x-y if x>=y else 0)
if __name__=='__main__':
  main()
### BUGGY CODE ###

S=input()
Q=int(input())
for i in range(Q):
    a=list(map(str,input().split()))
    if  int(a[0])==1:
        S=S[::-1]
    elif int(a[0])!=1 and int(a[1])==1:
        S=a[2]+S
    elif int(a[0])!=1 and int(a[1])==2:
        S=S+a[2]
    a.clear
print(S)

### FIXED CODE ###

import collections as co
S=input()
Q=int(input())
count=0
back=str()
front=str()
judge=True
for i in range(Q):
    a=list(map(str,input().split()))   
    if  int(a[0])==1:
        if judge==True:
            judge=False
        else:
            judge=True
    elif int(a[0])==2 and int(a[1])==1:
        if judge==True:
            front=a[2]+front
        if judge==False:
            back=back+a[2]
    else:
        if judge==True:
            back=back+a[2]
        if judge==False:
            front=a[2]+front
    a.clear
if judge==True:
    S=front+S+back
if judge==False:
    S=front+S+back
    S=S[::-1]
print(S)
### BUGGY CODE ###

from collections import deque
n = int(input())
l = deque()

for i in range(n):
    cmd = input().split()
    if cmd[0] == 'insert':
        l.append(cmd[1])
    if cmd[0] == 'find':
        sl = set(l)
        if len( sl & {cmd[1]} ) == 1:
            print('yes')
        else:
            print('no')

### FIXED CODE ###

from collections import defaultdict

d = defaultdict(lambda: 0)

N = int(input())

for _ in range(N):
    ord, str = input().split()
    if ord == 'insert':
        d[str] = 1
    else:
        if str in d:
            print('yes')
        else:
            print('no')
### BUGGY CODE ###

N = int(input())
t = []
a = []
for i in range(0,N):
	tokuhyousuu = list(map(int,input().split()))
	t.append(tokuhyousuu[0])
	a.append(tokuhyousuu[1])

T = t[0]
A = a[0]
r = 1
r_2 = 1

for j in range(0,N):
	if(T<=t[j] and A<=a[j]):
		T = t[j]
		A = a[j]

	elif(T>t[j] and A>a[j]):
		for k in range(1000000000000000000000000):
			if(T<=(k*t[j])):
				r = k
				break

		for l in range(1000000000000000000000000):
			if(A<=(l*a[j])):
				r_2 = l
				break

		T = t[j]*(max(r,r_2))
		A = a[j]*(max(r,r_2))


	elif(T>t[j]):
		for p in range(1000):
			if(T<=(p*t[j])):
				T = p*t[j]
				A = p*a[j]
				break

	elif(A>a[j]):
		for q in range(1000):
			if(A<=(q*a[j])):
				T = q*t[j]
				A = q*a[j]
				break
print(T+A)

### FIXED CODE ###

N = int(input())
t = []
a = []
for i in range(0,N):
	tokuhyousuu = list(map(int,input().split()))
	t.append(tokuhyousuu[0])
	a.append(tokuhyousuu[1])

T = 1
A = 1

for j in range(0,N):
	if(T<=t[j] and A<=a[j]):
		T = t[j]
		A = a[j]

	elif(T>t[j] and A>a[j]):
		if(T%t[j] == 0):
			r_1 = T//t[j]
		else:
			r_1 = T//t[j] + 1

		if(A%a[j] == 0):
			r_2 = A//a[j]
		else:
			r_2 = A//a[j] + 1

		r = max(r_1,r_2)

		T = t[j]*r
		A = a[j]*r


	elif(T>t[j]):
		if(T%t[j]==0):
			r = T//t[j]
		else:
			r = T//t[j]+1
		
		T = t[j]*r
		A = a[j]*r

	elif(A>a[j]):
		if(A%a[j] == 0):
			r = A//a[j]
		else:
			r = A//a[j]+1			
		T = t[j]*r
		A = a[j]*r

print(T+A)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

# coding: utf-8
# Your code here!
h,w=map(int,input().split())

field=[]
m=[]
INF=10**4

for i in range(h):
    row=list(input())
    field.append(row)
    m.append([INF for i in range(w)])

dx=[1,0,-1,0]
dy=[0,1,0,-1]

queue=[]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":
            m[i][j]=0
            queue.append([i,j])
while len(queue)>0:
    y,x=queue.pop(0)
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=ny<h and 0<=nx<w:
            if m[ny][nx]>m[y][x]+1 and field[ny][nx]==".":
                m[ny][nx]=m[y][x]+1
                queue.append([ny,nx])

ans=0

for i in range(h):
    ans=max(ans,max(m[i]))

print(ans)

### FIXED CODE ###

h,w=map(int,input().split())
INF=10**10
a=[[INF for i in range(w)] for j in range(h)]
ans=0
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="#":
            a[i][j]=0
            
for i in range(h):
    for j in range(w):
        k=a[i][j]+1

        if i!=h-1:
            if k<a[i+1][j]:
                a[i+1][j]=k
        if j!=w-1:
            if k<a[i][j+1]:
                a[i][j+1]=k

for i in range(h):
    for j in range(w):
        k=a[-1-i][-1-j]+1
        if i!=h-1:
            if k<a[-i-2][-j-1]:
                a[-i-2][-j-1]=k

        if j!=w-1:        
            if k<a[-i-1][-j-2]:
                a[-i-1][-j-2]=k

for i in range(h):
    ans=max(ans,max(a[i]))
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# なんこか入力
n,m = map(int, input().split())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [0]*(n)
c1 = [0]
c2 = [0]
bb=0
c2[0]=1
for i in range(0,n) :
    bb = ( bb+a[i] ) % m
    if bb == 0:
        c2[0] += 1
    else:
        if bb in c1:
            c2[c1.index(bb)] += 1
        else:
            c1.append(bb)
            c2.append(1)
    
    
answer = 0
#print(c1)
#print(c2)
for i in range(0,len(c2)):
    cc = c2[i]
    if cc > 1:
        answer +=  (cc * (cc-1) // 2 )

print(answer)



### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# なんこか入力
n,m = map(int, input().split())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [0]*(n)
c ={0:1}
bb=0
for i in range(0,n) :
    bb = ( bb+a[i] ) % m
    c[bb] = c.get(bb,0) + 1
    
    
answer = 0
#print(c)

for i,j in c.items():
    if j > 1:
        answer +=  (j * (j-1) // 2 )

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


H, N = map(int, input().split())
ab_list = [list(map(int, input().split())) for _ in range(N)]

max_a = max(a for a,b in ab_list)
W = H + 1 + max_a
dp = [0] * W

for i in range(W):
    dp[i] = 10**9
    for a,b in ab_list:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H-1:]))

### FIXED CODE ###


H, N = map(int, input().split())
ab_list = [list(map(int, input().split())) for _ in range(N)]

max_a = max(a for a,b in ab_list)
W = H + 1 + max_a
dp = [0] * W

for i in range(W):
    dp[i] = min(dp[i-a]+b for a,b in ab_list)

print(min(dp[H-1:]))
### BUGGY CODE ###

from collections import Counter
n=int(input())
s=[]
for _ in range(n):
    s.append(input())
c = Counter(s)
ans=[]
for i,j in c.items():
    if j == max(c.values()):
        ans.append(i)
print("\n".join(sorted(ans)))

### FIXED CODE ###

from collections import Counter
n=int(input())
s=[]
for _ in range(n):
    s.append(input())
c = Counter(s)
ans=[]
max_vote = max(c.values())
for i,j in c.items():
    if j == max_vote:
        ans.append(i)
print("\n".join(sorted(ans)))
### BUGGY CODE ###

A, B, C = map(int, input().split())
K = int(input())

i = 0
while i < K:
    if B <= A:
        B *= 2
        i += 1
    else:
        if C <= B:
            C *= 2
            i += 1

if A < B < C:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

A, B, C = map(int, input().split())
K = int(input())

for i in range(K):
    if B <= A:
        B *= 2
    else:
        if C <= B:
            C *= 2

if A < B < C:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n = int(input())
mod = 10**9+7
num = [ int(v) for v in input().split() ]
bits = [ 0 for i in range(100) ]
num_bin_len = []
for i in num:
    t = bin(i)[2:][::-1]
    num_bin_len.append(len(t))
    for j, v in enumerate(t):
        bits[j] += int(v)

binmax = max(num_bin_len)+1
pow_2_list = [ pow(2,i,mod) for i in range(100) ]


ans = 0
for i, v in enumerate(bits[:binmax]):
    ans += v * (n-v)  * pow_2_list[i] 
print(ans % mod)


### FIXED CODE ###

n = int(input())
mod = 10**9+7
num = [ int(v) for v in input().split() ]
bits = [ 0 for i in range(100) ]

for i in num:
    j = 0
    while i > 0:
        if i % 2 == 1:
            bits[j] += 1
        i //= 2
        j += 1


binmax = 0
for i in range(100):
    if bits[i] > 0:
        binmax = i
binmax += 2


pow_2_list = []
q = 1
for i in range(100):
    pow_2_list.append(q)
    q *= 2
    q %= mod


ans = 0
for i, v in enumerate(bits[:binmax]):
    ans += v * (n-v)  * pow_2_list[i] 
print(ans % mod)