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

from collections import defaultdict
row=defaultdict(int)
col=defaultdict(int)
H,W,M=map(int,input().split())
matrix=[[1 for i in range(W)] for j in range(H)]
for i in range(M):
    h,w=map(int,input().split())
    row[h]+=1
    col[w]+=1
    matrix[h-1][w-1]=0
#print(row)
#print(col)
#for i in matrix:
#    print(*i)
temp=list(row.items())
temp.sort(key=lambda x:x[1])
a,b=temp[-1][0],temp[-1][1]
cnt=0
for i in range(W):
    temp=0
    if matrix[a-1][i]==0:
        temp=(b+col[i+1]-1)
    else:
        temp=(b+col[i+1])
    cnt=max(cnt,temp)
print(cnt)

### FIXED CODE ###

from collections import defaultdict
row=defaultdict(int)
col=defaultdict(int)
H,W,M=map(int,input().split())
#matrix=[[1 for i in range(W)] for j in range(H)]
matrix=defaultdict(bool)
for i in range(M):
    h,w=map(int,input().split())
    row[h-1]+=1
    col[w-1]+=1
    matrix[(h-1,w-1)]=True
#print(row)
#print(col)
#for i in matrix:
#    print(*i)
temp=list(row.items())
temp.sort(key=lambda x:x[1])
a,b=temp[-1][0],temp[-1][1]
cnt=0
for i in range(W):
    temp=0
    if matrix[(a,i)]:
        temp=(b+col[i]-1)
    else:
        temp=(b+col[i])
    cnt=max(cnt,temp)
#print(cnt)
temp=list(col.items())
temp.sort(key=lambda x:x[1])
a,b=temp[-1][0],temp[-1][1]
cnt2=0
for i in range(H):
    temp=0
    if matrix[(i,a)]:
        temp=(b+row[i]-1)
    else:
        temp=(b+row[i])
    cnt2=max(cnt2,temp)
print(max(cnt,cnt2))
### BUGGY CODE ###

H, W, N = map(int, input().split())
sh, sw = map(int, input().split())

S = input()
T = input()

def canTakaWin(toS, isInc, toT, R, c):
    mask = ((1 << (R + 1)) - 1) ^ 1
    now = 1 << c

    for s, t in zip(S, T):
        if s == toS:
            now = (now << 1) if isInc else (now >> 1)
        now &= mask

        direct = 0
        for i, k in enumerate(toT):
            if k == t:
                direct = (-1)**i
        if direct != 0:
            now |= (now << 1) if direct > 0 else (now >> 1)
        now &= mask

    return now == 0

ans = False
ans = ans or canTakaWin('U', False, 'DU', H, sh)
ans = ans or canTakaWin('D', True, 'DU', H, sh)
ans = ans or canTakaWin('L', False, 'RL', W, sw)
ans = ans or canTakaWin('R', True, 'RL', W, sw)

print('NO' if ans else 'YES')


### FIXED CODE ###

H, W, N = map(int, input().split())
sr, sc = map(int, input().split())
S = input()
T = input()

left = 1
right = W
bottom = 1
top = H

if S[-1] == 'L':
    left += 1
elif S[-1] == 'R':
    right -= 1
elif S[-1] == 'U':
    bottom += 1
elif S[-1] == 'D':
    top -= 1

for i in range(N - 1)[:: -1]:
    if T[i] == 'L':
        right = min(W, right + 1)
    elif T[i] == 'R':
        left = max(1, left - 1)
    elif T[i] == 'U':
        top = min(H, top + 1)
    elif T[i] == 'D':
        bottom = max(1, bottom - 1)

    if S[i] == 'L':
        left += 1
    elif S[i] == 'R':
        right -= 1
    elif S[i] == 'U':
        bottom += 1
    elif S[i] == 'D':
        top -= 1

    if left > right or bottom > top:
        print('NO')
        break
else:
    if left <= sc <= right and bottom <= sr <= top:
        print('YES')
    else:
        print('NO')
### BUGGY CODE ###

n,k=map(int,input().split())
ans=n
while True:
  if ans>=abs(ans-k):
    ans=abs(ans-k)
  else:
    break
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
print(min(n,n-k*(n//k),abs(n-k*(n//k)-k)))
### BUGGY CODE ###

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

a=sorted(a,reverse=True)
for _ in range(m):
    a[0]=a[0]//2
    a=sorted(a,reverse=True)

print(sum(a))

### FIXED CODE ###

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

for i in range(n):
    a[i]*=-1

heapq.heapify(a)
for _ in range(m):
    x=heapq.heappop(a)*(-1)
    x=x//2
    heapq.heappush(a,-x)

print(sum(a)*(-1))
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(key = lambda x: -x)

if n == 1:
    print(a[0]//2**m)
    exit()

# idx = 0
while m > 0:
    a[0] //= 2
    idx = 0
    m -= 1
    if m <= 0: break
    while idx < n-1 and a[idx] < a[idx+1]:
        a[idx], a[idx+1] = a[idx+1],a[idx]
        idx += 1
    # idx = 0

print(sum(a))



### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(lambda x: -int(x), input().split()))
heapq.heapify(a)

if n == 1:
    print(-a[0]//2**m)
    exit()

for _ in range(m):
    heapq.heappush(a, -1*(-heapq.heappop(a)//2))

print(-sum(a))
### BUGGY CODE ###

N = int(input())
P = input()
I = P.count("1")
Df = int(P,2)
Ans = [0] * (N+1)
#print(solve(N,cnt))

for i in range(1, N+1):
    p = format(i,"b").count("1")
    tmp = i % p
    Ans[i] = Ans[tmp] +1 
#print("Ans = ", Ans)

for i in range(N-1):
    if P[i] == "1":
        tmp = Df - 2**(N-i-1)
        cur = I - 1
    else:
        tmp = Df + 2**(N-i-1)
        cur = I + 1 
    if cur == 0:
        print(0)
        continue
    print(Ans[tmp%cur]+1)

if P[N-1] == "1":
    tmp = Df - 1
    cur = I - 1
else:
    tmp = Df + 1
    cur = I + 1
if cur == 0:
    print(0)
else:
    print(Ans[tmp%cur]+1)

### FIXED CODE ###

N = int(input())
x = input()

cnt_x = x.count("1")
px10 = 0
nx10 = 0
ans = [0] * (N+1)

for i in range(1, N+1): #Nまで先に出しておく
    popcnt = format(i,"b").count("1")
    fx = i % popcnt
    ans[i] = ans[fx] + 1

for i in range(N):
    px10 += (int(x[i]) * pow(2,N-1-i, cnt_x+1)) % (cnt_x+1)#0⇒1となった場合の合計
    if cnt_x != 0 and cnt_x != 1:
        nx10 += int(x[i])*pow(2,N-1-i,cnt_x-1) % (cnt_x-1)#1⇒0となった場合の合計
#print(px10)
#print(nx10)
for i in range(N):
    if x[i] == "0":
        xi10 = (px10+pow(2,N-1-i,cnt_x+1))%(cnt_x+1)
        print(ans[xi10]+1)
    else:
        if cnt_x != 1:
            xi10 = (nx10-pow(2,N-1-i,cnt_x-1))%(cnt_x-1)
            print(ans[xi10]+1)
        else:
            print(0)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
data=[[int(i) for i in input().split()] for i in range(m)]
data.sort(key=lambda x:x[1],reverse=True)
a.sort(reverse=True)
ans=0
flag=True
for i in range(n):
  if data[0][1]<a[0] or flag==False:
    ans+=a[0]
    a=a[1:]
  else:
    ans+=data[0][1]
    data[0][0]-=1
    if data[0][0]==0:
      if len(data)>1:
        data=data[1:]
      else:
        flag=False
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=[[1,int(i)] for i in input().split()]
data=[[int(i) for i in input().split()] for i in range(m)]
data.extend(a)
data.sort(key=lambda x:x[1],reverse=True)
ans=0
flag=True
index=0
while n>0:
  tmp=min(data[index][0],n)
  ans+=data[index][1]*tmp
  n-=tmp
  index+=1
print(ans)
### BUGGY CODE ###

from sys import stdin
import math


def main():
    n, k = list(map(int, input().split()))
    A = list(map(int, stdin.readline().split()))
    roots = []
    roots.append(A)
    maxLoop = math.ceil(math.log(k)/math.log(2))
    for _ in range(1, maxLoop+1):
        roots_tmp = [None] * n
        for j in range(n):
            roots_tmp[j] = roots[-1][roots[-1][j]-1]
        roots.append(roots_tmp)

    position = 1
    for i in range(maxLoop+1):
        if k & (1 << (maxLoop-i)):
            position = roots[-1-i][position-1]
    print(position)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin


def main():
    n, k = list(map(int, input().split()))
    A = list(map(int, stdin.readline().split()))
    roots = [1]
    position = 0
    for _ in range(n):
        position = A[roots[-1]-1]
        A[roots[-1]-1] = - position
        if position < 0:
            break
        roots.append(position)

    x = roots.index(-position)
    y = len(roots) - x

    if k <= x:
        print(roots[k])
    elif k > x:
        print(roots[x + ((k-x) % y)])


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

N,S=map(int,input().split())
A=list(map(int,input().split()))
dp=[[0 for i in range(S+1)]for j in range(N+1)]
# dp[0]=[-1 for i in range(S)]
dp[0][0]=1
for i in range(N):
    for j in range(S+1):
        if j-A[i]>=0:
            dp[i+1][j]+=dp[i][j-A[i]]+2*dp[i][j]
        else:
            dp[i+1][j]+=2*dp[i][j]
print(dp[N][S]%998244353)

### FIXED CODE ###

from copy import copy
import numpy as np
N,S=map(int,input().split())
A=list(map(int,input().split()))
dp=np.zeros(S+100,np.int64)
dp[0]=1
for i in range(N):
    buf=copy(dp)
    dp=2*dp
    dp[A[i]:]+=buf[:-A[i]]
    dp%=998244353
print(dp[S]%998244353)
### BUGGY CODE ###

n = int(input())
power = 1
for i in range(1, n + 1):
	power *= i
print(power % (10 ** 9 + 7))


### FIXED CODE ###

import math

n = int(input())
print(math.factorial(n) % (10 ** 9 + 7))
### BUGGY CODE ###

def solve(k):
    a_mod = 0
    for i in range(1000000):
        a_mod += 7 * pow(10, i, k)
        a_mod %= k
        if a_mod == 0:
            return i + 1
    return -1


def main():
    k = int(input())
    res = solve(k)
    print(res)


def test():
    assert solve(101) == 4
    assert solve(2) == -1
    assert solve(999983) == 999982


if __name__ == "__main__":
    test()
    main()


### FIXED CODE ###

def solve(k):
    a_mod = 0
    for i in range(1000000):
        a_mod += 7 * pow(10, i, k)
        a_mod %= k
        if a_mod == 0:
            return i + 1
    return -1


def main():
    k = int(input())
    res = solve(k)
    print(res)


def test():
    assert solve(101) == 4
    assert solve(2) == -1
    assert solve(999983) == 999982


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

N=int(input())
X=[int(input())]
for i in range(N-1):
  a=int(input())
  if a>max(X):
    X[-1]=a
  elif min(X)>=a:
    X.insert(0,a)
  else:
    for j,x in enumerate(X):
      if x>=a:
        X[j-1]=a
        break
print(len(X))

### FIXED CODE ###

N=int(input())
from collections import deque
d = deque([int(input())]) 
import bisect

for i in range(N-1):
  a=int(input())
  if a>d[-1]:
    d[-1]=a
  elif d[0]>=a:
    d.appendleft(a)
  else:
    i=bisect.bisect_left(d,a)
    d[i-1]=a
print(len(d))
### BUGGY CODE ###

case = []
i = j = 0

while True:
    num = int(input())
    if num == 0:
        break
    case.append(num)
    i += 1

while j < i:
    print("Case",end=' ')
    print(j+1,end=': ')
    print(case[j])

### FIXED CODE ###

case = []
i = j = 0

while True:
    num = int(input())
    if num == 0:
        break
    case.append(num)
    i += 1

while j < i:
    print("Case",end=' ')
    print(j+1,end=': ')
    print(case[j])
    j += 1
### BUGGY CODE ###

from collections import deque
import sys
from collections import defaultdict
import copy
# input = sys.stdin.readline



H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
gone = [[0] * W for _ in range(H)]
cot = 0
que = deque()

que_count = 0
for h in range(H):
    for w in range(W):
        if C[h][w] == "#":
            gone[h][w] = 1
            que.append((h,w))
            que_count += 1
            cot += 1
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans  = 0
nq = 0
while cot != H*W:
    while que_count != 0 and cot != H*W:
        h,w = que.popleft()
        que_count -= 1

        for temp in go:
            # この時，実際に行くのかは不明
            gx,gy = temp
            nx = w + gx
            ny = h + gy

            if 0<= nx < W and 0<= ny < H and gone[ny][nx] != 1: #行って無かったら，行く
                # この時に実際に移動する
                gone[ny][nx] = 1
                que.append( (ny,nx))
                nq += 1
                cot += 1
    que_count = nq
    nq = 0
    ans += 1
print(ans)





### FIXED CODE ###

from collections import deque
import sys
from collections import defaultdict
import copy
# input = sys.stdin.readline



H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
gone = [[0] * W for _ in range(H)]
cot = 0
que = deque()

que_count = 0
for h in range(H):
    for w in range(W):
        if C[h][w] == "#":
            gone[h][w] = 1
            que.append((h,w))
            que_count += 1
            cot += 1
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans  = 0
nq = 0
while cot != H*W:
    while que_count != 0 and cot != H*W:
        h,w = que.popleft()
        que_count -= 1

        for temp in go:
            # この時，実際に行くのかは不明
            gx,gy = temp
            nx = w + gx
            ny = h + gy

            if 0<= nx < W and 0<= ny < H and gone[ny][nx] != 1: #行って無かったら，行く
                # この時に実際に移動する
                gone[ny][nx] = 1
                que.append( (ny,nx))
                nq += 1
                cot += 1
    que_count = nq
    nq = 0
    ans += 1
print(ans)
### BUGGY CODE ###

import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())
cy -= 1
cx -= 1
gy -= 1
gx -= 1
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())
q = deque()
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e + 1)
                    continue
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e + 1))
print(-1 if ans == float("inf") else ans)


### FIXED CODE ###

import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())
cy -= 1
cx -= 1
gy -= 1
gx -= 1
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())
q = deque()
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e + 1)
                    continue
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e + 1))
print(-1 if ans == float("inf") else ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for i in range(Q):
    l, r = map(int, input().split())
    print(len(S[l-1:r].split('AC')) - 1)


### FIXED CODE ###

N, Q = map(int, input().split())
S = list(input())
t = [0] * (N+1)
cnt = 0
for i in range(1,N):
    if S[i-1] == 'A' and S[i] == 'C':
        cnt += 1
    t[i] = cnt
t[-1] = t[-2]
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

def boundary_find(array, limit):
    while 1:
        center = len(array) // 2
        if array[center] <= limit:
            array = array[center:]
        else:
            array = array[:center]
        if len(array) == 1:
            break
    return array[0]

n, c, k = map(int, input().split())
tList = [int(input()) for _ in range(n)]
tList.sort()
count = 0
while 1:
    limit = tList[0] + k
    last = min(c, len(tList))
    if tList[last - 1] <= limit:
        mark = last - 1
    else:
        mark = tList.index(boundary_find(tList, limit))
    count += 1
    tList = tList[mark + 1:]
    if tList == []:
        break
print(count)

### FIXED CODE ###

def boundary_find(array, limit):
    ceil = len(array) - 1 
    floor = 0
    while 1:
        center = (ceil + floor) // 2
        if array[center] <= limit:
            floor = center
        else:
            ceil = center
        if ceil - floor == 1:
            break
    return ceil

n, c, k = map(int, input().split())
tList = [int(input()) for _ in range(n)]
tList.sort()
count = 0
first = 0
while 1:
    limit = tList[first] + k
    last = min(first + c, n)
    if tList[last - 1] <= limit:
        mark = last
    else:
        mark = boundary_find(tList, limit)
    count += 1
    first = mark
    if first == n:
        break
print(count)
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())
    rev = 0
    for i in range(q):
        Q = input().split()
        if Q[0]=="1":
            rev = (rev+1)%2
        else:
            if Q[1]=='1':
                if rev==0:
                    s = Q[2]+s
                else:
                    s = s+Q[2]
            else:
                if rev==0:
                    s = s+Q[2]
                else:
                    s = Q[2]+s
    if rev==0:
        print(s)
    else:
        print(s[::-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

s = input()
q = int(input())

t = 0
l = ''
r = ''
for i in range(q):
    query = input()
    if query == '1':
        if t == 1:
            t = 0
        else:
            t = 1
    else:
        if query[2] == '1':
            if t == 0:
                l = query[4:]+l
            else:
                r = r+query[4]
        else:
            if t == 0:
                r = r+query[4]
            else:
                l = query[4] + l
s = l+s+r
if t == 1:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

s = int(input())
a = []
count = 0
for j in range(s):
        a.append(int(input()))
b = sorted(a)
for i in range(s):
    if  (i + b.index(a[i]))%2 == 1:
            count += 1
count = count//2 + count%2
print(count)

### FIXED CODE ###

s = int(input())
a = []
b = []
o = 0
count = 0
for j in range(s):
        if j%2 == 0:
                a.append(int(input()))
        else:
                b.append(int(input()))
a = sorted(a)
c = sorted(a+b)
for i in range(s):
        if o == len(a):
                break
        if a[o] == c[i]:
                if i%2 == 1:
                        count += 1
                o += 1
print(count)
### BUGGY CODE ###

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

for i in range(Q):
    l, r = map(int, input().split())
    print(string[l-1:r].count("AC"))


### FIXED CODE ###

N, Q = map(int, input().split())
string = input()
 
counter = [0]*(N+1)

for i in range(N):
    counter[i+1] = counter[i] + (1 if string[i:i+2] == "AC" else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(counter[r-1] - counter[l-1])
### BUGGY CODE ###

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

ans = N
for i in range(N + 1):
    left_num = S[:i].count('#')
    right_num = S[i:].count('.')
    ans = min(ans, (left_num + right_num))
    if right_num == 0:
        break
print(ans)

### FIXED CODE ###

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

all_black_num = S.count('#')
all_white_num = N - all_black_num

if all_black_num == 0 or all_white_num == 0:
    ans = 0
else:
    left_black_num = 0
    left_white_num = 0
    right_white_num = all_white_num - left_white_num
    right_black_num = all_black_num - left_black_num
    ans = left_black_num + right_white_num
    for i, c in enumerate(S):
        if c == '#':
            left_black_num += 1
        elif c == '.':
            left_white_num += 1
        right_white_num = all_white_num - left_white_num
        right_black_num = all_black_num - left_black_num
        ans = min(ans, left_black_num + right_white_num)
        if right_black_num == N - i - 1:
            break
print(ans)
### BUGGY CODE ###

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

position = 1
exp = [1]
count = 0

if n >= k:
  for i in range(k):
    position = a[position - 1]
  print(position)
else:
  for i in range(k):
    position = a[position - 1]
    count += 1
    if exp.count(position) == 0:
      exp.append(position)
    else:
      break
  init = exp.index(position)
  res = (k - init) % (count - init)
  print(exp[init + res])

### FIXED CODE ###

n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
 
position = 1
exp1 = [0] * n
exp1[0] = 1
exp = [1]
count = 0
 
if n >= k:
  for i in range(k):
    position = a[position - 1]
  print(position)
else:
  for i in range(k):
    position = a[position - 1]
    count += 1
    if exp1[position - 1] == 0:
      exp.append(position)
      exp1[position - 1] += 1
    else:
      break
  init = exp.index(position)
  res = (k - init) % (count - init)
  print(exp[init + res])
### BUGGY CODE ###

def solve():
    s = input()
    n = len(s)
    mod = 2019

    reminder = [0]*mod
    pre_rem = 0

    for i in range(n):
        pre_rem = (int(s[n-i-1])*pow(10, i) + pre_rem) % mod
        reminder[pre_rem] += 1

    ans = reminder[0]  # そのまま割り切れる奴ら
    for rem_num in reminder[1:]:  # _nC_2をしてる
        if rem_num >= 2:
            ans += (rem_num * (rem_num -1))//2
    print(ans)
    
solve()


### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)
### BUGGY CODE ###

import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n = ni()
v = nl()
c = nl()
ans = 0
for i in range(2 ** n):
    lis = list(bin(i)[2:].zfill(n))
    tmp = 0
    for l in range(len(lis)):
        tmp += int(lis[l]) * (v[l] - c[l])
    ans = max(ans, tmp)
print(ans)


### FIXED CODE ###

import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n = ni()
v = nl()
c = nl()
ans = 0
for i in range(n):
    if v[i] - c[i] > 0:
        ans += v[i] - c[i]
print(ans)
### BUGGY CODE ###

import numpy as np

N,M = list(map(int,input().split()))
Hlist = list(map(int,input().split()))
# Mlist = [list(map(int,input().split())) for _ in range(M)]

adj = [[0 for _ in range(N)] for _ in range(N)]

# for line in Mlist:
for _ in range(M):
    line = list(map(int,input().split()))
    adj[line[0]-1][line[1]-1] = 1
    adj[line[1]-1][line[0]-1] = 1

# # for i in range(N):
# #     adj[i][i] = 1

Hmatrix = [Hlist for _ in range(N)]
target = np.array(Hmatrix)*np.array(adj)
index_list = [i for i in range(len(adj)) if sum(adj[i]) != 0]

count = N - len(index_list)
for i in index_list:
    if max(target[i]) < Hlist[i]:
        count += 1
print(count)

### FIXED CODE ###

import numpy as np

N,M   = list(map(int,input().split()))
Hlist = list(map(int,input().split()))
Hdict = {i:Hlist[i] for i in range(len(Hlist))}
# adj = [[0 for _ in range(N)] for _ in range(N)]

# for line in Mlist:
bad_set = set()
for _ in range(M):
    line = list(map(int,input().split()))
    if Hdict[line[0]-1] <= Hdict[line[1]-1]:
        bad_set.add(line[0])
    if Hdict[line[1]-1] <= Hdict[line[0]-1]:
        bad_set.add(line[1])
print(N-len(bad_set))
### BUGGY CODE ###

a,b,n = map(int,input().split())
mx = 0
for i in range(1,n+1):
    front = int((a*i)/b)
    back = int(i/b)*a
    mx = max(mx,front-back)
print(mx)

### FIXED CODE ###

a,b,n = map(int,input().split())
mn = min(n,b-1)
front = int((a*mn)/b)
back = int(mn/b)*a
print(front-back)