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

import heapq

def myprim_heap(graph, n):
    #始点sから各頂点への最短距離
    INF = 10**9
    d = [INF] * n
    used = [False] * n #True:未確定
    s = 0
    d[s] = 0
    used[s] = True
    res = 0
    edgelist = []
    for e in graph[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge[1]]:
            continue
        res += minedge[0]
        v = minedge[1]
        used[v] = True
        for e in graph[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist, e)
    return res


n = int(input()) 
graph = [[] for _ in range(n)]
ixy = [[i] + [int(x) for x in input().split()] for i in range(n)]

ixy = sorted(ixy, key=lambda x:x[1])
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d = ixy[i+1][1] - ixy[i][1]
    graph[j].append([d,k])
    graph[k].append([d,j])

ixy = sorted(ixy, key=lambda x:x[2])
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d = ixy[i+1][2] - ixy[i][2]
    graph[j].append([d,k])
    graph[k].append([d,j])

res = myprim_heap(graph, n)
print(res)

### FIXED CODE ###

from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

edge = set()
for key in [itemgetter(1),itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge.add((i1,i2,d))
    
# csr形式に直す
row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(N,N))

# 最小全域木
from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
answer = tree.sum()
print(answer)
### BUGGY CODE ###

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

L,R =[],[]
for i in range(M):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)

p,q = [],[]
for i in range(Q):
    pp,qq = map(int,input().split())
    p.append(pp)
    q.append(qq)

cnt = 0
for i in range(Q):
    x = p[i]
    y = q[i]
    for j in range(M):
        l = L[j]
        r = R[j]
        if x <= l and y >= r:
            cnt += 1
    print(cnt)
    cnt = 0


### FIXED CODE ###

N,M,Q = map(int,input().split())
LR = [ list(map(int,input().split())) for i in range(M)]
pq = [ list(map(int,input().split())) for i in range(Q)]

lr = [ [0]*(N+1) for i in range(N+1)]
for i in range(M):
    l,r = LR[i][0],LR[i][1]
    lr[l][r] += 1

for i in range(N):
    for j in range(N):
        lr[i][j+1] += lr[i][j]

for i in range(Q):
    ans = 0
    p,q = pq[i][0],pq[i][1]
    for i in range(p,q+1):
        ans += (lr[i][q] - lr[i][p-1])
    print(ans)
### BUGGY CODE ###

N = int(input())
S = [None] * N
for i in range(N):
    S[i] = input()
nums = [None] * N
for i, s in enumerate(S):
    tmp = [0] * 26
    for c in s:
        tmp[ord(c)-97] += 1
    nums[i] = ' '.join(map(str, tmp))

ans = 0
for i, s_i in enumerate(nums):
    for s_j in nums[i+1:]:
        if s_i == s_j:
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = [None] * N
for i in range(N):
    S[i] = input()
nums = [None] * N
for i, s in enumerate(S):
    tmp = [0] * 26
    for c in s:
        tmp[ord(c)-97] += 1
    nums[i] = ' '.join(map(str, tmp))

ans = 0
checker = dict()

for s in reversed(nums):
    #print(s)
    if s in checker:
        ans += checker[s]
        checker[s] += 1
    else:
        checker[s] = 1
print(ans)
### BUGGY CODE ###

BILLS = [10000, 5000, 1000]


def distribute_rest(length, rest, result=[], current=[]):
    if length == 1:
        current.append(rest)
        result.append(current)
    else:
        for i in range(rest + 1):
            result = distribute_rest(
                length - 1, rest - i, result, list(current) + [i])
    return result


def main(n, y):
    bill_counts = None
    for counts in distribute_rest(len(BILLS), n):
        price = sum([bill * count for bill, count in zip(BILLS, counts)])
        if price == y:
            bill_counts = counts
            break
    if not bill_counts:
        bill_counts = [-1, -1, -1]
    print(' '.join([str(x) for x in bill_counts]))


if __name__ == "__main__":
    n, y = [int(x) for x in input().split()]
    main(n, y)


### FIXED CODE ###

BILLS = [10000, 5000, 1000]


def calc_price(counts):
    return sum([bill * count for bill, count in zip(BILLS, counts)])


def main(n, y):
    for c1 in range(n + 1):
        for c2 in range(0, n - c1 + 1):
            counts = [c1, c2, n - c1 - c2]
            if calc_price(counts) == y:
                print(' '.join([str(c) for c in counts]))
                return
    print('-1 -1 -1')


if __name__ == "__main__":
    n, y = [int(x) for x in input().split()]
    main(n, y)
### BUGGY CODE ###

N = int(input())
count = 0
word = []
def verify_anagrams(w1, w2):
    f = lambda y: "".join(sorted(map(lambda x: x.replace(' ', '').lower(), y)))
    return f(w1) == f(w2)

for _ in range(N):
    word.append(input())

for i in range(N - 1):
    for j in range(i + 1,N):
        if verify_anagrams(word[i], word[j]):
            count += 1
print(count)

### FIXED CODE ###

#from Collections import Counter

N = int(input())
count = 0
word = {}
def str_sort(str):
    f = lambda y: "".join(sorted(map(lambda x: x.replace(' ', '').lower(), y)))
    return f(str)
for _ in range(N):
    sorted_str = str_sort(input())
    if sorted_str not in word:
        word[sorted_str] = [0]
        word[sorted_str].append(1)
    else:
        if word[sorted_str] == 0:
            word[sorted_str][0] = 1
        else:
            word[sorted_str][0] += word[sorted_str][1]
            word[sorted_str][1] += 1
            #word[sorted_str] = word[sorted_str][0] + word[sorted_str][1]
total = sum(
    v[0] for v in word.values()
)
#print(word)
print(total)
### BUGGY CODE ###

# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import numpy as np
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right

INF = float("INF")

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

N, K = s_inpl()
a = inpl()

dp = [INF] * N

dp[0] = 0

for i in range(1, N):
    for j in range(1, K+1):
        if j - i > 0:
            continue
        dp[i] = min(dp[i], dp[i-j] + abs(a[i] - a[i-j]))

print(dp[N-1])

### FIXED CODE ###

# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

# import math
# import numpy as np
# import copy
# from collections import defaultdict, Counter
# from itertools import product
# from bisect import bisect_left, bisect_right

INF = float("INF")

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

N, K = s_inpl()
a = inpl()

dp = [INF] * N

dp[0] = 0

for i in range(1, N):
    for j in range(1, K+1):
        if j - i > 0:
            continue
        dp[i] = min(dp[i], dp[i-j] + abs(a[i] - a[i-j]))

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

M=10**9+7
n,m=map(int,input().split())
l=[int(input())-1 for _ in range(m)]
s,t=0,1
for i in range(n):
  if i in l: s,t=t,0
  else: s,t=t,(s+t)%M
print(t)

### FIXED CODE ###

mod = 10**9+7
n, m = map(int, input().split())
l = [int(input()) for _ in range(m)]

t2 = 0
t1 = 1

for i in range(1,n+1):
  if l == [] or i != l[0]:
    t0 = (t2+t1)%mod
  else:
    l.pop(0)
    t0 = 0
  t2 = t1
  t1 = t0

print(t0)
### BUGGY CODE ###

import sys
from itertools import product
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
h, w, k = map(int, readline().split())
CHOCO = [list(map(int, line.rstrip().decode())) for line in readlines()]
INF = 10**5
it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    cnt = sum(map(int, x))
    agg = [[0]*(w) for _ in range(cnt+1)]
    *ls, = map(int, x+('1',))
    for i in range(w):
        prev = c = 0
        for j, split in enumerate(ls):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]
    tmp = [0]*(cnt+1)
    for xyz in zip(*agg):
        cannot_split = False
        can_continue = True
        for i, x in enumerate(xyz):
            if x > k:
                cannot_split = True
                break
            if x+tmp[i] > k:
                can_continue = False
                break

        if cannot_split:
            break

        if can_continue:
            for i, x in enumerate(xyz):
                tmp[i] += x
                continue
        else:
            for i, x in enumerate(xyz):
                tmp[i] = x
            cnt += 1

    if cannot_split:
        continue

    ans = min(ans, cnt)
print(ans)


### FIXED CODE ###

from itertools import product
h, w, k = map(int, input().split())
CHOCO = [list(map(int, input())) for _ in range(h)]
INF = 10**5

it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    cnt = sum(map(int, x))
    agg = [[0]*(w) for _ in range(cnt+1)]
    *ls, = map(int, x+('1',))
    for i in range(w):
        prev = c = 0
        for j, split in enumerate(ls):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]

    tmp = [0]*(cnt+1)
    cannot_split = False

    for xyz in zip(*agg):
        cannot_split = False
        can_continue = True
        for i, x in enumerate(xyz):
            if x > k:
                cannot_split = True
                break
            if x+tmp[i] > k:
                can_continue = False
                break

        if cannot_split:
            break

        if can_continue:
            for i, x in enumerate(xyz):
                tmp[i] += x
                continue
        else:
            for i, x in enumerate(xyz):
                tmp[i] = x
            cnt += 1

    if cannot_split:
        continue

    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

from sys import stdin

def main():

    input = stdin.readline

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

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

    itta_list = []
    idou_num = 0

    pos = 0

    for i in range(K):
        # itta_list記憶
        if pos not in set(itta_list):
            itta_list.append(pos)
        else:
            idou_num = i
            break

        # 次の街へ
        pos = A[pos] - 1
    else:
        ans_num = pos + 1
        print(ans_num)
        return

    roop_list = itta_list[itta_list.index(pos):]

    amari = (K - idou_num) % len(roop_list)

    ans_pos = roop_list[amari] + 1

    print(ans_pos)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin

def main():

    input = stdin.readline

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

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

    itta_set = set()
    itta_list = []
    idou_num = 0

    pos = 0

    for i in range(K):
        # itta_list記憶
        if pos not in itta_set:
            itta_set.add(pos)
            itta_list.append(pos)
        else:
            idou_num = i
            break

        # 次の街へ
        pos = A[pos] - 1
    else:
        ans_num = pos + 1
        print(ans_num)
        return

    roop_list = itta_list[itta_list.index(pos):]

    amari = (K - idou_num) % len(roop_list)

    ans_pos = roop_list[amari] + 1

    print(ans_pos)

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

N,M = map(int,input().split())
li = []
sets = set()
for m in range(M):
  x,y = input().split()
  li.append([int(x), y])
  if y == 'AC':
    sets.add(int(x))

ac = len(sets)
wa = 0

for s in sets:
  for i in li:
    if i[0] == s and i[1] == 'WA':
      wa += 1
    if i[0] == s and i[1] == 'AC':
      break

print('{0} {1}'.format(ac, wa))

### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)

N,M = map(int,input().split())
li = []
for m in range(M):
  x,y = input().split()
  li.append([int(x), y])

sets = set()

ac = 0
wa = 0

for i in li:
  if i[1] == 'AC':
    if i[0] not in sets:
      sets.add(i[0])
      ac += 1
      wa += d[i[0]]

  else:
    if i[0] not in sets:
      d[i[0]] += 1

print('{} {}'.format(ac, wa))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
count = []
for i in range(0,n):
	counter = 0
	for k in range(0,n):
		if (a[i] - 1) <= a[k] <= (a[i] + 1):
			counter += 1
	count.append(counter)
	
mx = max(count)
print('{0}'.format(mx))

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
count = collections.Counter(a)
max = 0
for i in count:
    if count[i] + count[i-1] + count[i+1] > max:
        max = count[i] + count[i-1] + count[i+1]
print(max)
### BUGGY CODE ###

from collections import Counter

def main():
    n = int(input())
    array_s = []
    array = []
    for i in range(n):
        array_s.append(input())

    for s in array_s:
        array.append(Counter(s))

    ans = 0
    for i in range(n):
        if not array:
            break
        alphabet = array[:][0]
        num = array.count(alphabet)-1
        if num <= 0:
            pass
        elif num <= 1:
            ans += 1
        else:
            ans += int((num+1)*num/2)
        for j in range(num+1):
            array.remove(alphabet)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    array_s = []
    array = []
    for i in range(n):
        array_s.append(input())

    for s in array_s:
        array.append(''.join(sorted(s)))
    array = sorted(array)
    ans = 0
    count = 1
    for i in range(n-1):
        if array[i] == array[i+1]:
            count += 1
            if i != n-2:
                continue
        ans += int(count*(count-1)/2)
        count = 1
    print(ans)


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

import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

import heapq

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

B = []

for a in A:
    i = 0
    while i < len(B) and B[i] >= a:
        i += 1

    if i != len(B):
        B[i] = a
    else:
        B.append(a)

print(len(B))

pass


### FIXED CODE ###

import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

import heapq

N = int(input())
A = []
for _ in range(N):
    A.append(-int(input()))

B = []

for a in A:
    i = bisect.bisect_right(B, a)
    if i != len(B):
        B[i] = a
    else:
        B.append(a)

# print(B)
print(len(B))

pass
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10**9)


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    graph = [[] for _ in range(N)]
    for i in range(M):
        graph[x[i]-1].append(y[i]-1)

    memo = {}

    def dfs(v):
        if v in memo:
            return memo[v]

        if graph[v]:
            res = max(dfs(child) for child in graph[v])
            memo[v] = res + 1
        else:
            res = 0
            memo[v] = 0

        return memo[v]

    print(max(dfs(i) for i in range(N)))


# 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
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10**9)


def dfs(v, graph, memo):
    if v in memo:
        return memo[v]

    if graph[v]:
        res = float("-inf")
        for child in graph[v]:
            res = max(res, dfs(child, graph, memo) + 1)
        memo[v] = res
    else:
        res = 0
        memo[v] = 0

    return memo[v]


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    graph = [[] for _ in range(N)]
    for i in range(M):
        graph[x[i]-1].append(y[i]-1)

    memo = {}

    res = float("-inf")
    for i in range(N):
        res = max(res, dfs(i, graph, memo))
    print(res)


# 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
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


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

n=int(input())
s = [0]*n
for i in range(n):
    s[i] = input()
dic = []
count = 1
for i in range(n):
    sw = 0
    if i == 0:
        dic.append(s[0])
    else:
        for name in dic:
            if str(name) == str(s[i]):
                sw = 1
        if sw == 0:
            dic.append(s[i])
            count += 1
print(count)

### FIXED CODE ###

n=int(input())
s = [0]*n
for i in range(n):
    s[i] = input()
print(len(set(s)))
### BUGGY CODE ###

def solve(_list,_k):
  start = 0
  _sum = -1
  for i in range(len(_list)-_k+1):
    s = sum(_list[i:i+_k])
    if _sum < s:
      _sum = s
      start = i

  ans = 0.
  for item in _list[start:start+_k]:
    ans += (item+1) / 2

  return ans


if __name__ == "__main__":
  _n, _k = map(int, input().split())
  _l = [int(i) for i in input().split()]

  result = solve(_l, _k)
  print(result)


### FIXED CODE ###

def solve(_list,_k):
  accumulate_list = [0.]
  for i in _list:
    accumulate_list.append((i+1)/2 + accumulate_list[-1])

  ans = -1.0
  for i in range(len(accumulate_list)-_k):
    ans = max(ans, accumulate_list[i+_k]-accumulate_list[i])
  return ans

if __name__ == "__main__":
  _n, _k = map(int, input().split())
  _l = [int(i) for i in input().split()]

  result = solve(_l, _k)
  print(result)
### BUGGY CODE ###

from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)


# def debug(var, name="hoge"):
#     print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
#     return


def main():
    MOD = 10**9 + 7
    S = list(input()[:-1])
    L = len(S)
    modsum = 0
    # 余り
    memo_prev = [0 for _ in range(13)]
    memo_prev[0] = 1
    memo = [0 for _ in range(13)]

    for i in range(L):
        memo = [0 for _ in range(13)]
        # 数字なら以前までの余りにたす
        if S[i].isnumeric():
            for m in range(13):
                cur = (10*m+int(S[i]))%13
                memo[cur] += memo_prev[m]
        # ?なら1~10の余りのケース全てをためす
        else:
            for n in range(10):
                for m in range(13):
                    cur = (10*m+n)%13
                    memo[cur] += memo_prev[m]
                    memo[cur] %= MOD
        memo_prev = memo.copy()
    print(memo[5])


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import exit, stderr, stdin
input = stdin.readline


def main():
    MOD = 10**9 + 7
    S = input()[:-1]
    L = len(S)
    # 余り
    memo = [0 for _ in range(13)]
    memo[0] = 1

    for i in range(L):
        memo_prev = [x for x in memo]
        memo = [0 for _ in range(13)]
        # 数字なら以前までの余りにたす
        if S[i].isnumeric():
            n = int(S[i])
            for m in range(13):
                cur = (10*m+n)%13
                memo[cur] += memo_prev[m]
        # ?なら1~10の余りのケース全てをためす
        else:
            for n in range(10):
                for m in range(13):
                    cur = (10*m+n)%13
                    memo[cur] += memo_prev[m]
            for m in range(13):
                memo[m] %= MOD
    print(memo[5])


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

import fractions
 
n = int(input())
a = list(map(int, input().split()))
 
num = a[0]
for i in range(1, n):
	num = (num // fractions.gcd(num, a[i]))*a[i]
 
ans = 0
for i in range(n):
	ans += (num//a[i]) 
print(ans%1000000007)

### FIXED CODE ###

import fractions
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for i in range(n):
	l = l // fractions.gcd(l, a[i])*a[i]
 
ans = 0
for i in range(n):
	ans += l//a[i]
print(ans%(10**9+7))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import product

n, m, q = map(int, readline().split())
abcd = [list(map(int, readline().split())) for _ in range(q)]
ans = 0
for bit in product([0, 1], repeat=q):
    cnt = 0
    aaa = []
    aaaa = []
    for i, (a, b, c, d) in enumerate(abcd):
        if bit[i] == 1:
            aaa.append([a, b, c])
    for a, b, c in aaa[::-1]:
        for aa, bb, cc in aaa:
            if aa == a and b < bb:
                aaaa.append([b, bb, cc - c])
            elif aa == a and b > bb:
                aaaa.append([bb, b, c - cc])
            if b == bb and aa > a:
                aaaa.append([a, aa, cc - c])
            elif b == bb and aa < a:
                aaaa.append([aa, a, c - cc])
    aaa += aaaa
    for i, (a, b, c, d) in enumerate(abcd):
        if bit[i] == 1:
            for aa, bb, cc in aaa:
                if (aa <= a < b <= bb and c > cc) or (a <= aa < bb <= b and c < cc):
                    if aa == a and bb == b and c == cc:
                        continue
                    else:
                        break
            else:
                cnt += d
    if ans < cnt:
        ans = cnt
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import combinations_with_replacement

n, m, q = map(int, readline().split())
abcd = [list(map(int, readline().split())) for _ in range(q)]
ans = 0
for seq in combinations_with_replacement(range(m), n):
    cnt = 0
    for a, b, c, d in abcd:
        if seq[b - 1] - seq[a - 1] == c:
            cnt += d
    ans = max(ans, cnt)
print(ans)