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

I = list(map(int, input().split()))
N = I[0]
K = I[1]
H = list(map(int, input().split()))
H = [0] + H

dp = [float('inf') for _ in range(N+1)]

dp[N] = 0
dp[N-1] = abs(H[N]-H[N-1])
for i in range(N-2,0,-1):
	for k in range(1,K+1):
		if i+k<=N:
			dp[i] = min(abs(H[i+k]-H[i])+dp[i+k], dp[i])

print(dp[1])

### FIXED CODE ###

I = list(map(int, input().split()))
N = I[0]
K = I[1]
H = list(map(int, input().split()))

dp = [float('inf') for _ in range(N+1)]

dp[N] = 0
for i in range(N-1,N-K-1,-1):
	if i>0:
		dp[i] = abs(H[i-1]-H[N-1])

for i in range(N-K-1,0,-1):
	for k in range(1,K+1):
		if i+k<=N:
			dp[i] = min(abs(H[i+k-1]-H[i-1])+dp[i+k], dp[i])

print(dp[1])
### BUGGY CODE ###

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

acc_list = []
for i in range(Q):
    acc_list.append(int(input()))

point_dict = {}
for i in range(1, N+1):
    point_dict[i] = K

for a in acc_list:
    for key, valu in point_dict.items():
        if a != key:
            point_dict[key] = valu - 1

for key, valu in point_dict.items():
    if valu <= 0:
        print('No')
    elif valu > 0:
        print('Yes')


### FIXED CODE ###

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

acc_list = []
for i in range(Q):
    acc_list.append(int(input()))

point_dict = {}
for i in range(1, N+1):
    point_dict[i] = 0

for a in acc_list:
    point_dict[a] += 1

for key, valu in point_dict.items():
    if (K - Q + valu) <= 0:
        print('No')
    elif (K - Q + valu) > 0:
        print('Yes')
### BUGGY CODE ###

def main():
    n=int(raw_input())
    ta=[map(int,raw_input().split()) for _ in xrange(n)]
    for i in xrange(1,n):
        tmp1=ta[i][0]
        tmp2=ta[i][1]
        if ta[i-1][0]>ta[i][0]:
            a=2
            while 1:
                tmp1=ta[i][0]*a
                tmp2=ta[i][1]*a
                if ta[i-1][0]<=tmp1 and ta[i-1][1]<=tmp2:
                    break
                a+=1
        if ta[i-1][1]>ta[i][1]:
            a=2
            while 1:
                tmp1=ta[i][0]*a
                tmp2=ta[i][1]*a
                if ta[i-1][0]<=tmp1 and ta[i-1][1]<=tmp2:
                    break
                a+=1
        ta[i][0]=tmp1
        ta[i][1]=tmp2
    print(ta[n-1][0]+ta[n-1][1])
main()

### FIXED CODE ###

def main():
    n=int(raw_input())
    ta=[map(int,raw_input().split()) for _ in xrange(n)]
    for i in xrange(1,n):
        if ta[i-1][0]>ta[i][0] and ta[i-1][1]>ta[i][1]:
            mx=max((ta[i-1][0]-1)/ta[i][0]+1,(ta[i-1][1]-1)/ta[i][1]+1)
            ta[i][0]=ta[i][0]*mx
            ta[i][1]=ta[i][1]*mx
        elif ta[i-1][0]>ta[i][0]:
            ta[i][1]=ta[i][1]*((ta[i-1][0]-1)/ta[i][0]+1)
            ta[i][0]=ta[i][0]*((ta[i-1][0]-1)/ta[i][0]+1)
        elif ta[i-1][1]>ta[i][1]:
            ta[i][0]=ta[i][0]*((ta[i-1][1]-1)/ta[i][1]+1)
            ta[i][1]=ta[i][1]*((ta[i-1][1]-1)/ta[i][1]+1)
    print(ta[n-1][0]+ta[n-1][1])
main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)

def dfs(v, o):
    ret = []
    ancestors.add(v)
    for c in G[v]:
        if c == o:
            ancestors.remove(v)
            return [[v]]
        elif c in ancestors:
            ancestors.remove(v)
            return []
        else:
            for a in dfs(c, o):
                ret.append([v] + a)
    ancestors.remove(v)
    return ret

for v in range(1, N+1):
    ancestors = set()
    for cand in dfs(v, v):
        cand = set(cand)
        for v in cand:
            cnt = 0
            for c in G[v]:
                if c in cand:
                    cnt += 1
            if cnt >= 2:
                break
        else:
            print(len(cand))
            print(*cand, sep='\n')
            exit()
print(-1)

### FIXED CODE ###

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

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)

def dfs(v, o):
    for c in G[v]:
        if c == o:
            return [v]
    for c in G[v]:
        if visited[c]:
            continue
        visited[c] = True
        ret = dfs(c, o)
        if ret:
            return [v] + ret

for v in range(1, N+1):
    visited = [False] * (N+1)
    cur = dfs(v, v)
    if cur:
        break
else:
    print(-1)
    exit()

while True:
    cur_set = set(cur)
    unused = None
    for i in range(len(cur)):
        u, v = cur[i], cur[(i+1) % len(cur)]
        for c in G[u]:
            if c == v:
                continue
            elif c in cur_set:
                unused = (i, cur.index(c))
                break

    if not unused:
        break
    else:
        t, s = unused
        nxt = []
        i = s
        while i != t:
            nxt.append(cur[i])
            i = (i + 1) % len(cur)
        nxt.append(cur[t])
        cur = nxt

print(len(cur))
print(*cur, sep='\n')
### BUGGY CODE ###

N=2*10**6+1
mod=10**9+7
fac=[1]*(N+1)
for i in range(1,N+1):
    fac[i]=fac[i-1]*i%mod
inv_fac=[1]*(N+1)
inv_fac[N]=pow(fac[N],mod-2,mod)
for i in range(N-1,0,-1):
    inv_fac[i]=inv_fac[i+1]*(i+1)%mod
def nCr(n,r):
    if n<=0 or r<0 or r>n:
        return 0
    return fac[n]*inv_fac[r]%mod*inv_fac[n-r]%mod

r1,c1,r2,c2=map(int,input().split())
w=r2-r1
h=c2-c1
ans=nCr(r1+c1,r1)
for i in range(r1+1,r2+1):
    ans=(ans+(nCr(i+c1,i)*nCr(r2-i+1+h,h)%mod))%mod
for i in range(c1+1,c2+1):
    ans=(ans+(nCr(i+r1,i)*nCr(c2-i+1+w,w)%mod))%mod
print(ans)

### FIXED CODE ###

N=2*10**6+1
mod=10**9+7
fac=[1]*(N+1)
for i in range(1,N+1):
    fac[i]=fac[i-1]*i%mod
inv_fac=[1]*(N+1)
inv_fac[N]=pow(fac[N],mod-2,mod)
for i in range(N-1,0,-1):
    inv_fac[i]=inv_fac[i+1]*(i+1)%mod
def nCr(n,r):
    if n<=0 or r<0 or r>n:
        return 0
    return fac[n]*inv_fac[r]%mod*inv_fac[n-r]%mod

r1,c1,r2,c2=map(int,input().split())
w=r2-r1
h=c2-c1
ans=nCr(r1+c1,r1)
for i in range(r1+1,r2+1):
    ans=(ans+(nCr(i+c1,i)*nCr(r2-i+1+h,h)%mod))%mod
for i in range(c1+1,c2+1):
    ans=(ans+(nCr(i+r1,i)*nCr(c2-i+1+w,w)%mod))%mod
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
# input = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
start = time.time()
N = int(input())
A = list(map(int, input().split(' ')))
Asum = [i+A[i] for i in range(N)]
Adif = [i-A[i] for i in range(N)]

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if Asum[i] == Adif[j]:
            ans += 1

print(ans)


### FIXED CODE ###

from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
# read = sys.stdin.buffer.read
# readline = sys.stdin.buffer.readline
# readlines = sys.stdin.buffer.readlines
input = sys.stdin.readline

start = time.time()
N = int(input())
A = list(map(int, input().split(' ')))
Asum = [i+A[i] for i in range(N)]
Adif = [i-A[i] for i in range(N)]

ans = 0
d = defaultdict(int)
for i in range(N):
    ans += d[Adif[i]]
    d[Asum[i]] += 1

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

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 16:49:00 2020

@author: matsui
"""

def cost(i,j):
    return abs(int(h[i])-int(h[j]))

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

dp=[0]*N
   
for i in range(1,N):
    tmp=[]
    for j in range(1,K+1):
        if i-j < 0 : break
        tmp.append(cost(i,i-j)+dp[i-j])
    dp[i]=min(tmp)
    
print(dp[N-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 16:49:00 2020

@author: matsui
"""



N,K=map(int,input().split())
h=[int(num) for num in input().split()]

dp=[0]*N
dp[1]=abs(h[0]-h[1])
   
def cost(h,N,K,dp):
    for i in range(2,N):
        dp[i]=min([abs(h[i]-h[j])+dp[j] for j in range(max(0, i-K), i)])
    return dp[-1]
    
print(cost(h,N,K,dp))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def compare(x):
  return x[0]


def find(x, lst):
  for value in lst:
    if value[0] == x:
      return True
  return False


n = int(input())
lst = [[0, 0, 0]]
for i in range(n):
  lst.append(list(map(int, input().split())))
lst.sort(key=compare)
x = lst[len(lst) - 1][0]
for i in range(1, x):
  if not find(i, lst):
    lst.append([i, -1, -1])
lst.sort(key=compare)

points = [[0, 0]]
flg = False
try:
  for i in range(1, x + 1):
    fix = False
    wk = []
    for j in range(len(points)):
      wk.append((points[j][0] + 1, points[j][1]))
      wk.append((points[j][0] - 1, points[j][1]))
      wk.append((points[j][0], points[j][1] + 1))
      wk.append((points[j][0], points[j][1] - 1))

      ps = (lst[i][1], lst[i][2])
      x = points[j][0]
      y = points[j][1]
      if (i == lst[i][0]) and (x >= 0) and (y >= 0) and ((x + 1, y) == ps or (x - 1, y) == ps or (x, y + 1) == ps or (x, y - 1) == ps):
        flg = True
        wk = [ps]
        break
    points = list(set(wk))
    if (i == lst[i][0]) and (lst[i][1] >= 0) and (not flg):
      break
finally:
  print('Yes') if flg else print('No')


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
points = []
for i in range(n):
  points.append(list(map(int, input().split())))

flg = False
for point in points:
  flg = (point[0] >= (point[1] + point[2])) and ((point[0] % 2 == 1) and ((point[1] + point[2]) % 2 == 1) or (point[0] % 2 == 0) and ((point[1] + point[2]) % 2 == 0))
  if not flg:
    break
print('Yes') if flg else print('No')
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = []
for j in range(1,N+1):
  for i in range(N):
    if A[i] == j:
      B.append(i+1)
for i in range(N):
  B[i] = str(B[i])
print(' '.join(B))

### FIXED CODE ###

#入力 人数N 入った順番A[i]
N = int(input())
A = list(map(int, input().split()))
#[入った順番 出席番号]のリストを作製
B = [[] for i in range(N)]
for i in range(N):
    B[i] = [A[i], i+1]
#入った順番(=最初の要素)早い順に並べる
B.sort()
#出席番号だけのリストを作製
ans = [0 for i in range(N)]
for i in range(N):
    ans[i] = B[i][1]
#リストの要素をスベース付きで全て表示
print(*ans)
### BUGGY CODE ###

n = int(input())
t = [int(input()) for _ in range(n)]

f, ans, x = 0, 1, 2

while x<=max(t):
    for i in range(n):
        if t[i]%x==0:
            t[i] //= x
            f = 1
    if f:
        ans *= x
        f = 0
    else:
        x += 1
for i in t:
    ans *= i
print(ans)


### FIXED CODE ###

n = int(input())
t = [int(input()) for _ in range(n)]


#a>b
def gcd(a, b):
    if b:
        return gcd(b, a%b)
    else:
        return a

def lcm(a, b):
    if a>b:
        g = gcd(a, b)
        return a*b//g
    else:
        g = gcd(b, a)
        return a*b//g

ans = 1
for i in range(n):
    ans = lcm(ans, t[i])

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

import math

A, B, N = map(int, input().split(' '))

_max = 0
for x in range(N, int(N/2), -1):
    
    num =math.floor(A * x / B) - A * math.floor(x/B) 
    # print(num)
    if  num > _max:
        _max = num

print(_max)

### FIXED CODE ###

import math

def floor(A, B, x):
    return math.floor(A * x / B) - A * math.floor(x/B) 

A, B, N = map(int, input().split(' '))
x = min(N, B-1)
print(floor(A,B,x))
### BUGGY CODE ###

n, ma, mb = map(int, input().split())
items = []
for i in range(n):
    item = list(map(int, input().split()))
    items.append(item)

# dp[iまでの薬品を使用して][aの重量][bの重量]を達成する最小の予算
dp = [[[float('inf')]*401 for j in range(401)] for i in range(41)]
dp[0][0][0] = 0

for i in range(n):
    a, b, c = items[i]
    for anow in range(400):
        for bnow in range(400):
            # 使わない
            dp[i+1][anow][bnow] = min(dp[i+1][anow][bnow], dp[i][anow][bnow])
            # 使う
            if 0<=anow+a<401 and 0<=bnow+b<401:
                dp[i+1][anow+a][bnow+b] = min(dp[i+1][anow+a][bnow+b], dp[i][anow][bnow]+c)
                

ans = float('inf')
for a in range(1, 401):
    for b in range(1, 401):
        if ma*b==mb*a:
            ans = min(ans, dp[n][a][b])
if ans == float('inf'):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n, ma, mb = map(int, input().split())
items = []
for i in range(n):
    item = list(map(int, input().split()))
    items.append(item)

# dp[iまでの薬品を使用して][aの重量][bの重量]を達成する最小の予算
dp = [[[float('inf')]*401 for j in range(401)] for i in range(41)]
dp[0][0][0] = 0

for i in range(n):
    a, b, c = items[i]
    for anow in range(400):
        for bnow in range(400):
            # 使わない
            dp[i+1][anow][bnow] = min(dp[i+1][anow][bnow], dp[i][anow][bnow])
            # 使う
            if 0<=anow+a<401 and 0<=bnow+b<401:
                dp[i+1][anow+a][bnow+b] = min(dp[i+1][anow+a][bnow+b], dp[i][anow][bnow]+c)
                

ans = float('inf')
for a in range(1, 401):
    for b in range(1, 401):
        if ma*b==mb*a:
            ans = min(ans, dp[n][a][b])
if ans == float('inf'):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

a,b,x=map(int, input().split())
ls=[num for num in range(a,b+1) if num%x==0]
print(len(ls))

### FIXED CODE ###

a,b,x=map(int, input().split())
print(b//x-(a-1)//x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# C - Many Requirements
import copy

n, m, q = map(int, input().split())
seq_arr = []

for i in range(1, m + 1):
	seq_arr.append([i])

for i in range(n):
	tmp_arr = []
	
	for s in seq_arr:
		for j in range(s[-1], m + 1):
			tmp_arr.append(s + [j])

	seq_arr = copy.deepcopy(tmp_arr)

queries = []

for i in range(q):
	a, b, c, d = map(int, input().split())
	queries.append([a-1, b-1, c, d])

ans = 0

for seq in seq_arr:
	sum = 0
	
	for query in queries:
		a, b, c, d = query
		
		if seq[b] - seq[a] == c:
			sum += d
			
	ans = max(ans, sum)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# C - Many Requirements
import copy

n, m, q = map(int, input().split())
seq_arr = []

for i in range(1, m + 1):
	seq_arr.append([i])

for i in range(n):
	tmp_arr = []
	
	for s in seq_arr:
		for j in range(s[-1], m + 1):
			tmp_arr.append(s + [j])

	seq_arr = copy.deepcopy(tmp_arr)

queries = []

for i in range(q):
	a, b, c, d = map(int, input().split())
	queries.append([a-1, b-1, c, d])

ans = 0

for seq in seq_arr:
	sum = 0
	
	for query in queries:
		a, b, c, d = query
		
		if seq[b] - seq[a] == c:
			sum += d
			
	ans = max(ans, sum)

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

import sys
input = sys.stdin.readline

def main():
    N,M,L = map(int,input().split())
    edge = [[float("inf") for _ in range(N)] for _ in range(N)]
    
    for _ in range(M):
        a,b,c = map(int,input().split())
        edge[a-1][b-1] = edge[b-1][a-1] = c
    
    for i in range(N):
        edge[i][i] = 0

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if (edge[j][k] > edge[j][i]+edge[i][k]):
                    edge[j][k] = edge[j][i]+edge[i][k]
    
    ref = [[float("inf") for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if edge[i][j] <= L:
                ref[i][j] = 1
            
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if (ref[j][k] > ref[j][i]+ref[i][k]):
                    ref[j][k] = ref[j][i]+ref[i][k]

    Q = int(input())
    for _ in range(Q):
        a,b = map(int,input().split())
        print(ref[a-1][b-1]-1 if ref[a-1][b-1] != float("inf") else -1)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

def main():
    N,M,L = map(int,input().split())
    edge = np.zeros((N,N))
    for _ in range(M):
        a,b,c = map(int,input().split())
        edge[a-1][b-1] = edge[b-1][a-1] = c
        
    length = floyd_warshall(edge,directed=False)
    ref = np.where(length<=L,1,0)
    ans = floyd_warshall(ref,directed=False)
    Q = int(input())
    for _ in range(Q):
        s,t = map(int,input().split())
        if ans[s-1][t-1] == float("inf"):
            print(-1)
        else:
            print(int(ans[s-1][t-1])-1)

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

import sys
from collections import deque

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [deque(rl()) for _ in range(N)]
answer = 0
match = 0
while True:
    used = set()
    bool = False
    for i in range(N):
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)


### FIXED CODE ###

import sys
import copy
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]

match = 0
candidate = []
used = set()
for i in range(N):    
    bool = False
    if len(A[i]) == 0:
        continue
    op = A[i][0] - 1
    if op in used or i in used:
        continue
    if A[op][0]-1 == i:
        used.add(i)
        used.add(op)
        candidate.extend([i, op])
        match += 1
        bool = True
        A[i].popleft()
        A[op].popleft()
answer = 1

while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

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

H,N=map(int,input().split())
hn=[]
for i in range(N):
  hn.append(list(map(int,input().split())))
dp=[[10**17]*(H+1) for _ in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
  for j in range(H+1):
    h,n=hn[i-1][0],hn[i-1][1]
    dp[i][j]=min(dp[i-1][j],dp[i][max(0,j-h)]+n)
print(dp[N][H])

### FIXED CODE ###

H,N=map(int,input().split())
a=[]
max_x=-10**10
for i in range(N):
  x,y=map(int,input().split())
  if x>max_x:
    max_x=x
  a.append([x,y])
  
dp = [0] * (H+max_x)
for i in range(0,H+max_x):
    if i==0:
        dp[i]=0
    else:
        dp[i]=min(dp[i-l[0]]+l[1] for l in a )
print(dp[H])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    s = input()
    count = 0

    for i in range(len(s)):
        if i == 0:
            count = s[1:].count('E')
        else:
            count = min(count, s[:i].count('W') + s[i + 1:].count('E'))

    print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    s = input()
    count = 0
    ws = [0] * n
    es = [0] * n

    for i in range(0, n):
        if s[i] == 'W':
            ws[i] = ws[i - 1] + 1
            es[i] = es[i - 1]
        else:
            es[i] = es[i - 1] + 1
            ws[i] = ws[i - 1]

    for i in range(len(s) - 1):
        if i == 0:
            count = es[-1] - es[1]
        else:
            count = min(count, (ws[i]) + (es[-1] - es[i + 1]))

    print(count)
### BUGGY CODE ###

n = int(input())
lis = []

for i in range(n):
	a = int(input())
	lis.append(a)

for i in range(n):
	x = lis.pop(i)
	print(max(lis))
	lis.insert(i,x)

### FIXED CODE ###

n = int(input())
lis = []

for i in range(n):
	a = int(input())
	lis.append(a)
kou = sorted(lis, reverse=True)

for i in range(n):
	if lis[i] < kou[0]:
		print(kou[0])
	else:
		print(kou[1])
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
o=[]
e=[]
for i in range(N):
    if i%2:
        o=o+[a[i]]
        e=[a[i]]+e
    else :
        o=[a[i]]+o
        e=e+[a[i]]
for i in o if N%2 else e:
    print(i,sep="",end=" ")

### FIXED CODE ###

N=int(input())
a=input().split()
print(*(a[::-2]+a[N%2::2]))
### BUGGY CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
# mod = 10**9 + 7

# n = int(input())
h, n = map(int, input().split())
# a = list(map(int, input().split()))
a, b = [0] * n, [0] * n

for i in range(n):
    a[i], b[i] = map(int,input().split())

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

for i in range(n):

    for j in range(h):

        dp[min(j+a[i], h)] = min(dp[min(j+a[i],h)], dp[j]+b[i])


print(dp[h])

### FIXED CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
# mod = 10**9 + 7

# n = int(input())
h, n = map(int, input().split())
# a = list(map(int, input().split()))
a, b = [0] * n, [0] * n

for i in range(n):
    a[i], b[i] = map(int,input().split())

dp = [10**9+7] * (h+1)
dp[0] = 0

for i in range(n):

    for j in range(h):

        dp[min(j+a[i], h)] = min(dp[min(j+a[i],h)], dp[j]+b[i])


print(dp[h])
### BUGGY CODE ###

#event sort
import bisect
N, Q = map(int, input().split())
events = []
for i in range(N):
    s,t,x = map(int, input().split())
    events.append([s-x, 1, x])
    events.append([t-x, -1, x])
events.sort()
sets = set()
for _ in range(Q):
    d = int(input())
    eventime = [event[0] for event in events]
    index = bisect.bisect_right(eventime, d)
    for _ in range(index):
        t, pm, x = events.pop(0)
        if pm == 1:
            sets.add(x)
        if pm == -1:
            sets.remove(x)
    if len(sets)==0:
        print(-1)
    else:
        print(min(sets))

### FIXED CODE ###

from bisect import bisect_left
N, Q = map(int, input().split())
consts = []
for _ in range(N):
    s,t,x = map(int, input().split())
    consts.append((x,s,t))
consts.sort()
D=[int(input()) for _ in range(Q)]
ans=[-1]*Q
jump=[-1]*Q
for x,s,t in consts:
    left=bisect_left(D,s-x)
    right=bisect_left(D,t-x)
    while left<right:
        if jump[left]==-1:
            ans[left]=x
            jump[left]=right
            left += 1
        else:
            left=jump[left]
print(*ans, sep='\n')
### BUGGY CODE ###

def main():
    N = int(input())
    a_list = list(map(int, input().split()))

    sum = 0
    for i in range(N-1):
        for j in range(i+1, N):
            if a_list[i] == a_list[j]:
                continue
            sum += a_list[i] ^ a_list[j]

    print(sum % (10**9+7))


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    t = [0]*60

    for a in a_list:
        for count, i in enumerate(reversed(format(a, "b"))):
            if i == "1":
                t[count] += 1

    sum = 0
    for i, count in enumerate(t):
        sum += 2 ** i * count * (N - count)
    print(sum % mod)


if __name__ == '__main__':
    main()