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

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
from functools import lru_cache

    
class Solution:
    def __init__(self,prices):
        self._max = 0
        self.prices = prices
    
    @lru_cache(None)
    def transaction(self, money, stock, i, _inner_max):
        if stock == 0 and money < _inner_max - 1:
            return
        if i == len(self.prices):
            self._max = max(self._max, money)
            return
        
        _stock = stock
        _money = money
        ## buy
        if money >= self.prices[i]:
            stock, money = divmod(money, self.prices[i])
            # print("buy",money,stock,i)
            self.transaction(money, stock, i + 1, _inner_max)
        # backtracking
        money,stock = _money,_stock

        ## sell
        if stock > 0:
            stock, money = 0, stock * self.prices[i] + money
            if money > _inner_max:
                _inner_max = money
                self.transaction(money, 0, i + 1, _inner_max)
        # backtracking
        money,stock = _money,_stock

        ## do nothing
        self.transaction(money, stock, i + 1, _inner_max)


def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]
    solver = Solution(A)
    solver.transaction(1000, 0, 0,1000)
    print(solver._max)
    

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
 

def maxProfit(prices) -> int:
    if len(prices) < 2:
        return 0
    ans = 1000
    for i in range(1,len(prices)):
        if prices[i] > prices[i - 1]:
            stock = ans // prices[i - 1]
            ans += stock * (prices[i] - prices[i - 1]) 
    return ans

def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]

    ans = maxProfit(A)
    print(ans)


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


"""
Writer: SPD_9X2

dpか?(なるほど)
左からi番目までの店でk個行くと決めた時の最小の時間？

at+b と xt+y があった時、at+bを先に取ったほうが最終的に小さくなる条件は
頑張って手計算すると
x/(1+y) < a/(1+b) なので、a/(1+b)が大きい方から貪欲していくのが正解っぽい？

→ただの貪欲は×
ただ、いくつか取るやつを選べば、その中では↑の式によって最適な取り方が決まる

→a/(1+b)の大きい方からしかとらないので、その順で使う、使わないでdpする
→O(N**2)

どうやってdpするか…

=========答えを見た========
a != 0なら指数関数的に増えるので、(最低で2倍)
回る店の数はせいぜい30にしかならない。
よって、a != 0に関して回る店の数とその最小値をdpした後、a == 0に関して調べればいい…
むずいけど分かるなぁ…(悔しい)

"""
import sys
N,T = map(int,input().split())

kab = []
azero = []

for i in range(N):

    a,b = map(int,input().split())

    if a == 0:
        azero.append(b)
    else:
        k = a/(1+b)
        kab.append([-1*k,a,b])


nt = 0
kab.sort()
dp = [float("inf")] * 30
dp[0] = 0

for k,a,b in kab:

    for i in range(28,-1,-1):

        dp[i+1] = min(dp[i+1] , 1 + dp[i] + a*(1+dp[i]) + b )

azero.sort()
dsum = [0]
for i in azero:
    dsum.append(dsum[-1] + 1 + i)

ans = 0
import bisect
for i in range(30):

    if dp[i] > T:
        continue

    else:
        ans = max(i + bisect.bisect_right(dsum,T-dp[i]) - 1 , ans )
    
print (ans)

### FIXED CODE ###

"""
Writer: SPD_9X2

dpか?(なるほど)
左からi番目までの店でk個行くと決めた時の最小の時間？

at+b と xt+y があった時、at+bを先に取ったほうが最終的に小さくなる条件は
頑張って手計算すると
x/(1+y) < a/(1+b) なので、a/(1+b)が大きい方から貪欲していくのが正解っぽい？

→ただの貪欲は×
ただ、いくつか取るやつを選べば、その中では↑の式によって最適な取り方が決まる

→a/(1+b)の大きい方からしかとらないので、その順で使う、使わないでdpする
→O(N**2)

どうやってdpするか…

=========答えを見た========
a != 0なら指数関数的に増えるので、(最低で2倍)
回る店の数はせいぜい30にしかならない。
よって、a != 0に関して回る店の数とその最小値をdpした後、a == 0に関して調べればいい…
むずいけど分かるなぁ…(悔しい)

"""
N,T = map(int,input().split())

kab = []
azero = []

for i in range(N):

    a,b = map(int,input().split())

    if a == 0:
        azero.append(b)
    else:
        k = a/(1+b)
        kab.append([-1*k,a,b])


nt = 0
kab.sort()
dp = [float("inf")] * 29
dp[0] = 0

for k,a,b in kab:

    for i in range(27,-1,-1):

        dp[i+1] = min(dp[i+1] , 1 + dp[i] + a*(1+dp[i]) + b )

azero.sort()
dsum = [0]
for i in azero:
    dsum.append(dsum[-1] + 1 + i)

ans = 0
import bisect
for i in range(29):

    if dp[i] > T:
        break

    else:
        ans = max(i + bisect.bisect_right(dsum,T-dp[i]) - 1 , ans )
    
print (ans)
### BUGGY CODE ###

x,y,z,K = map(int, input().split())
abc = [sorted(list(map(int, input().split())), reverse=True) for i in range(3)]

ans = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if (i+1)*(j+1)*(k+1) <= K:
                ans.append(abc[0][i]+abc[1][j]+abc[2][k])
for i in sorted(ans)[::-1][:K]:
    print(i)

### FIXED CODE ###

from heapq import heappop, heappush

x,y,z,k = map(int, input().split())
abc = [sorted(list(map(int, input().split())), reverse=True) for i in range(3)]
heap = [[-sum(abc[i][0] for i in range(3)), (0,0,0)]]


cnt = 0
used = set()
while cnt < k:
    score, (a,b,c) = heappop(heap)
    if (a,b,c) in used:
        continue
    print(-score)
    used.add((a,b,c))
    cnt += 1
    for i in range(3):
        na = a+int(i==0)
        nb = b+int(i==1)
        nc = c+int(i==2)
        if 0<=na<x and 0<=nb<y and 0<=nc<z:
            nscore = 0
            for ind, j in enumerate([na,nb,nc]):
                nscore -= abc[ind][j]
            heappush(heap,[nscore, (na,nb,nc)])
### BUGGY CODE ###

n=int(input())
alpha=[chr(i) for i in range(97, 97+26)]
d={i:[[],[],[],[],[],[],[],[],[],[]] for i in alpha}
ans=0
for _ in range(n):
    s=input()
    if s not in d[s[0]][len(s)-1]:
        d[s[0]][len(s)-1].append(s)
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
alpha=[chr(i) for i in range(97, 97+26)]
d={i:[{0},{0},{0},{0},{0},{0},{0},{0},{0},{0}] for i in alpha}
ans=0
for _ in range(n):
    s=input()
    if s not in d[s[0]][len(s)-1]:
        d[s[0]][len(s)-1]|={s}
        ans+=1
print(ans)
### BUGGY CODE ###

from itertools import groupby
s=list(input())
ans=[0]
for k,v in groupby(s):
  d=len(list(v))
  x= -1 if k==">" else 1 
  ad=list(range(d+1))[::x]
  ans=ans[:-1]+[max(ans[-1],ad[0])]+ad[1:]
print(sum(ans))  

### FIXED CODE ###

from itertools import groupby

s = list(input())
f = 0
ans = 0
for k,v in groupby(s):
  d = len(list(v))
  left = d if k==">" else 0
  right = d if k=="<" else 0
  if f>left:
    ans += d*(d+1)//2 - left
  else:
    ans += -1*f + d*(d+1)//2  
  f = right 
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

INF = 10**18

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
C = [input() for _ in range(H)]

queue = deque()
queue.append((x1, y1))

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

dist = [[INF for j in range(W)] for i in range(H)]
dist[x1][y1] = 0

while queue:
    x, y = queue.popleft()
    for i in range(4):
        for k in range(K):
            nx = x + (k + 1) * dx[i]
            ny = y + (k + 1) * dy[i]
            if not (0 <= nx < H and 0 <= ny < W):
                break
            if C[nx][ny] == '@':
                break
            if dist[nx][ny] < dist[x][y] + 1:
                break
            if dist[nx][ny] != INF:
                continue
            dist[nx][ny] = dist[x][y] + 1
            queue.append((nx, ny))

print(dist[x2][y2] if dist[x2][y2] != INF else -1)

### FIXED CODE ###

from collections import deque

INF = 10**18

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
C = [input() for _ in range(H)]

queue = deque()
queue.append((x1, y1))

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

dist = [[INF for j in range(W)] for i in range(H)]
dist[x1][y1] = 0

while queue:
    x, y = queue.popleft()
    for i in range(4):
        for k in range(K):
            nx = x + (k + 1) * dx[i]
            ny = y + (k + 1) * dy[i]
            if not (0 <= nx < H and 0 <= ny < W):
                break
            if C[nx][ny] == '@':
                break
            if dist[nx][ny] <= dist[x][y]:
                break
            if dist[nx][ny] != INF:
                continue
            dist[nx][ny] = dist[x][y] + 1
            queue.append((nx, ny))

print(dist[x2][y2] if dist[x2][y2] != INF else -1)
### BUGGY CODE ###

count=0
mainasu=0
num=int(input())
An=[int(i) for i in input().split()]
for i in An:
    mainasu+=1
    
    for w in range(num-mainasu):
        
        if i==An[w+mainasu]:
            count=1
            break
    
if 0==count:
    print("YES")
    
else :
    print("NO")

### FIXED CODE ###

def duplication(lis):
    return len(lis) == len(set(lis)) 

num=int(input())
An=[int(i) for i in input().split()]


if duplication(An) == True:
    print("YES")
    
else :
    print("NO")
### BUGGY CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10 + 2 * 10 ** 5)

n, m = map(int, input().split())

color = [None] * (n + 1)
for i in range(n + 1):
    color[i] = i

def root(x):
    global color

    if color[x] == x:
        return x
    return root(color[x])

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    color[rx] = ry

for i in range(m):
    a, b = map(int, input().split())
    unite(a, b)

cnt = defaultdict(int)
for i in range(n):
    cnt[root(i + 1)] += 1
print(max(cnt.values()))

### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10 + 2 * 10 ** 5)
 
n, m = map(int, input().split())
 
color = [None] * (n + 1)
for i in range(n + 1):
    color[i] = i
 
def root(x):
    global color
 
    if color[x] == x:
        return x
    color[x] = root(color[x])
    return color[x]
 
def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    color[rx] = ry
 
for i in range(m):
    a, b = map(int, input().split())
    unite(a, b)
 
cnt = defaultdict(int)
for i in range(n):
    cnt[root(i + 1)] += 1
print(max(cnt.values()))
### BUGGY CODE ###

# テスト対象（ABC081A - Placing Marbles (https://atcoder.jp/contests/abs/tasks/abc081_a)
H,W = map(int, input().split())
A = 0
dp = []
mat = []
for h in range(H):
    dpr = [-1] * W
    for w, x in zip(range(W), input()):
        if x == "#":
            dpr[w] = 0
            mat += [(h, w, 0)]
    dp += [dpr]

def search(dp, mat, conf, nH, nW, cnt):
    if not conf:
        return
    if dp[nH][nW] < 0 or cnt+1<dp[nH][nW]:
        if dp[nH][nW] < 0:
            mat.insert(0, (nH, nW, cnt+1))
        dp[nH][nW] = cnt+1

i = 0
while len(mat) > 0:
    h, w, cnt = mat.pop()

    i+=1
    search(dp, mat, h > 0, h - 1, w, cnt)
    search(dp, mat, h < H-1, h + 1, w, cnt)
    search(dp, mat, w > 0, h , w - 1, cnt)
    search(dp, mat, w < W-1, h , w + 1, cnt)

import numpy as np
print(np.max(dp))


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

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

h, w = map(int, input().split())
c = [input() for i in range(h)]
INF = 10 ** 9


ans = 0
dq = [[0] * (h + 1) for i in range(h + 1)]
dp = [[INF] * (h + 1) for i in range(h + 1)]
for wi in range(w - 1):
    for diff in range(h + 1):
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i][wi] == c[i + diff][wi + 1])
        dq[0 + diff][0] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            dq[i + 1 + diff][i + 1] = dq[i + diff][i] - (c[h - i - 1 - diff][wi] == c[h - i - 1][wi + 1])
            
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i + diff][wi] == c[i][wi + 1])
        dq[0][0 + diff] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            dq[i + 1][i + 1 + diff] = dq[i][i + diff] - (c[h - i - 1 - diff][wi + 1] == c[h - i - 1][wi])  
    for i in range(h + 1):
        for j in range(h + 1):
            dp[i][j] = INF
    dp[0][0] = 0
    for i in range(h + 1):
        for j in range(h + 1):
            if i + 1 < h + 1:
                dp[i + 1][j] = min(dp[i][j] + dq[i][j], dp[i + 1][j])
            if j + 1 < h + 1:
                dp[i][j + 1] = min(dp[i][j] + dq[i][j], dp[i][j + 1])
    ans += dp[-1][-1]

print(ans)
    

### FIXED CODE ###

def solve(k):
    dp = [[0] * (h + 1) for i in range(h + 1)]
    for i in range(h):
        for diff in range(h - i):
            dp[i + 1][i + 1 + diff] = dp[i][i + diff] + (s[i + diff][k] == s[i][k + 1])
            dp[i + 1 + diff][i + 1] = dp[i + diff][i] + (s[i][k] == s[i + diff][k + 1])

    dq = [[INF] * (h + 1) for i in range(h + 1)]
    dq[0][0] = 0
    for i in range(h):
        dq[i + 1][0] = dq[i][0] + dp[h - i][h]
        dq[0][i + 1] = dq[0][i] + dp[h][h - i]  
    for i in range(h):
        for j in range(h):
            dq[i + 1][j + 1] = min(dq[i + 1][j] + dp[h - (i + 1)][h - j],
                                   dq[i][j + 1] + dp[h - i][h - (j + 1)])

    return dq[h][h]


h, w = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 5
OFFSET = 500

ans = 0
for i in range(w - 1):
    ans += solve(i)
    
print(ans)
### BUGGY CODE ###

import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)

    ans[v] = min(ans[v], d)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    if d + dd < dp[v, s + c]:
        dp[v, s + c] = d + dd
        heapq.heappush(heap, (d + dd, v, s + c))

print(*ans[2:], sep='\n')


### FIXED CODE ###

import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)

    ans[v] = min(ans[v], d)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    sc = min(s + c, 50 * N + 10)
    if d + dd < dp[v, sc]:
        dp[v, sc] = d + dd
        heapq.heappush(heap, (d + dd, v, sc))

print(*ans[2:], sep='\n')
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

ans = 0
for i in range(n // r + 1):
  for j in range(n // g + 1):
    t = i * r + j * g
    if t > n:
      continue
    if n - t == 0:
      ans += 1
    elif (n - t) % b == 0:
      ans += 1

print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(N // R + 1):
  for j in range((N - i * R) // G + 1):
    ball = i * R + j * G
    if N == ball:
      ans += 1
    elif (N - ball) % B == 0:
      ans += 1

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

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


import numpy as np


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return np.array(ret_r, dtype='int')


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = np.zeros(n, dtype='int')
ans = 0
for a in A:
    n_1_ls += ret_binary(a)


for i, n_1 in enumerate(n_1_ls):
    num_sonoketa = n_1 * (N - n_1)
    ans += (((2**i) % MOD) * num_sonoketa)
    ans %= MOD
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return ret_r


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
for a in A:
    tmp = ret_binary(a)
    for i in range(n):
        n_1_ls[i] += tmp[i]


for i, n_1 in enumerate(n_1_ls):
    num_sonoketa = n_1 * (N - n_1)
    ans += (((2**i) % MOD) * num_sonoketa)
    ans %= MOD
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(x) for x in input().split()]
f=[int(x) for x in input().split()]

a.sort()
f.sort(reverse=True)

l,u=-1,f[0]*a[-1]
while l+1<u:
  m=(l+u)//2
  s=0
  for i in range(n):
    s+= a[i]-m//f[i] if a[i]>m//f[i] else 0
  if s<=k:
    u=m
  else:
    l=m

print(u)

### FIXED CODE ###

import numpy as np

n,k=map(int,input().split())
a=[int(x) for x in input().split()]
f=[int(x) for x in input().split()]

a.sort()
f.sort(reverse=True)

A=np.array(a)
F=np.array(f)
S=sum(a)

l,u=-1,f[0]*a[-1]
while l+1<u:
  m=(l+u)//2
  s=0
  if S-np.minimum(A,m//F).sum()<=k:
    u=m
  else:
    l=m

print(u)
### BUGGY CODE ###

s=input()
m=len(s)

ans=0
for i in range(m+1):
    for j in range(i+4,m+1):
        num=int(s[i:j])
        if num%2019==0:ans +=1
print(ans)

### FIXED CODE ###

from collections import Counter
s=input()[::-1]
DP=[0]

num,point=0,1
for i in s:
    num +=int(i)*point
    num %=2019
    DP.append(num)
    point *=10
    point %=2019

ans=0
DP=Counter(DP)
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)
### BUGGY CODE ###

import sys
import heapq
sys.setrecursionlimit(10**6)

n, m = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
k = 0

pqs = []
edge = [[] for _ in range(n)]
for i in range(m):
    x, y = [int(item) for item in input().split()]
    edge[x].append(y)
    edge[y].append(x)

def dfs(n):
    kind[n] = k
    heapq.heappush(pqs[k], a[n])
    for item in edge[n]:
        if kind[item] != -1:
            continue
        dfs(item)

kind = [-1] * n
for i, item in enumerate(kind):
    if item == -1:
        pqs.append([])
        dfs(i)
        k += 1

if k == 1:
    print(0)
    exit()
    
ans = 0
for i in range(k):
    val = heapq.heappop(pqs[i])
    ans += val
pqs = sum(pqs, [])
pqs.sort()
for i in range(k-2):
    if i > len(pqs) - 1:
        print("Impossible")
        exit()
    ans += pqs[i]
print(ans)

### FIXED CODE ###

import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

def input():
    return sys.stdin.readline()[:-1]

n, m = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
k = 0

pqs = []
edge = [[] for _ in range(n)]
for i in range(m):
    x, y = [int(item) for item in input().split()]
    edge[x].append(y)
    edge[y].append(x)

def dfs(n):
    kind[n] = k
    heappush(pqs[k], a[n])
    for item in edge[n]:
        if kind[item] == -1:
            dfs(item)

kind = [-1] * n
for i, item in enumerate(kind):
    if item == -1:
        pqs.append([])
        dfs(i)
        k += 1

if k == 1:
    print(0)
    exit()
    
ans = 0
for i in range(k):
    val = heappop(pqs[i])
    ans += val
pqs = [flatten for inner in pqs for flatten in inner] 
pqs.sort()
for i in range(k-2):
    if i > len(pqs) - 1:
        print("Impossible")
        exit()
    ans += pqs[i]
print(ans)
### BUGGY CODE ###

H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    dp = [max(B) * H] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for n in range(N):
            hp = min(h + A[n], H)
            dp[hp] = min(dp[hp], dp[h] + B[n])
    return dp[H]

print(ibis(H, A, B))

### FIXED CODE ###

H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    dp = [max(B) * H] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for n in range(N):
            hp = min(h + A[n], H)
            dp[hp] = min(dp[hp], dp[h] + B[n])
    return dp[H]

print(ibis(H, A, B))
### BUGGY CODE ###

A,B,Q=map(int,input().split())
s=[int(input()) for i in range(A)]
t=[int(input()) for i in range(B)]
for q in range(Q):
    X=int(input())
    x_t=[X-b for b in t]
    a=[abs(i) for i in x_t]
    l1=min(a)
    if -l1 in x_t:
        l1=-l1
    x_s=[X-b for b in s]
    b=[abs(i) for i in x_s]
    l2=min(b)
    if -l2 in x_s:
        l2=-l2
    print(min(abs(l1)+min([abs(X-l1-b) for b in s]),abs(l2)+min([abs(X-l2-b) for b in t])))



### FIXED CODE ###

import bisect
INF=10**18
A,B,Q=map(int,input().split())
s=[int(input()) for i in range(A)]
t=[int(input()) for i in range(B)]
s=[-INF]+s+[INF]
t=[-INF]+t+[INF]
for q in range(Q):
    X=int(input())
    t1=bisect.bisect_right(t,X)
    s1=bisect.bisect_right(s,X)
    res=INF
    for T in [t[t1],t[t1-1]]:
        for S in [s[s1],s[s1-1]]:
            ans1=abs(X-T)+abs(S-T)
            ans2=abs(X-S)+abs(S-T)
            res=min(res,ans1,ans2)
    print(res)