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

N, M = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
B = [0] * M
C = [0] * M
for i in range(M):
    B[i], C[i] = [int(i) for i in input().strip().split()]

for i in range(M):
    A.sort()
    _B, _C = B[i], C[i]
    for j in range(0, _B):
        if A[j] < _C:
            A[j] = _C
print(sum(A))


### FIXED CODE ###

N, M = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
A.sort()

BC = [[0, 0] for _ in range(M)]
for j in range(M):
    BC[j][0], BC[j][1] = [int(i) for i in input().strip().split()]
BC.sort(key=lambda x: x[1])

res = 0
cnt = 0
i = N - 1
j = M - 1
while True:
    if cnt == N:
        break

    if j == -1:
        res += A[i]
        i -= 1
    elif A[i] > BC[j][1]:
        res += A[i]
        i -= 1
    elif A[i] <= BC[j][1]:
        res += BC[j][1]
        BC[j][0] -= 1
        if BC[j][0] == 0:
            j -= 1
    else:
        raise ValueError
    cnt += 1
print(res)
### BUGGY CODE ###

a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]

ma = 0
for i in range(a[0]-a[1]+1):
    c=b[i:i+a[1]]  #K個取りだす 
    ma=max(ma,sum(c))

print((ma+a[1])/2)

### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
exp=list(map(lambda x: (int(x)+1)/2,input().split()))
l=np.cumsum(exp)
 
ans=l[k-1]
for i in range(0,n-k):
  x=l[i+k]-l[i]
  ans=max(ans,x)
print(ans)
### BUGGY CODE ###

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

total = 1
for a in li:
  total *= a
  
if 10 ** 18 < total:
  total = -1
  
print(total)

### FIXED CODE ###

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

total = 1
li.sort()
for a in li:
    if a == 0:
        total = 0
        break
    total *= a
    if 10 ** 18 < total:
        total = -1
        break
print(total)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    S = input()
    N = len(S)

    S = [int(s) if s!="?" else -1 for s in S ]
    dp = [[0] * 13 for _ in range(N+1)]

    s = S[0]
    if s == -1:
        for j in range(10):
            dp[0][j] += 1
    else:
        dp[0][s%13] += 1
    for i in range(1,N):
        s = S[i]
        X = [s]
        if s == -1:
            X = range(10)

        for j in range(0,13):
            ten_j = j*10
            for x in X:
                k = (ten_j+x)%13
                dp[i][k] += dp[i-1][j]
                # print(i,j,k)

    # print(dp)
    print(dp[N-1][5] % (10**9+7))



if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    S = input()
    N = len(S)
    MOD = 10**9+7

    # S = [int(s) if s!="?" else -1 for s in S ]
    dp = [[0] * 13 for _ in range(N+1)]

    s = S[0]
    if s == "?":
        for j in range(10):
            dp[0][j] += 1
    else:
        dp[0][int(s)%13] += 1
    for i in range(1,N):
        s = S[i]
        if s == "?":
            for j in range(0,13):
                for x in range(10):
                    k = (j*10+x)%13
                    dp[i][k] += dp[i-1][j]
                    dp[i][k] %= MOD
        else:
            for j in range(0,13):
                k = (j*10+int(s))%13
                dp[i][k] += dp[i-1][j]
                dp[i][k] %= MOD


    print(dp[N-1][5])


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

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

g = [[0 for j in range(n)] for i in range(n)]

for _ in range(m):
    l, r = map(int, input().split())
    g[l - 1][r - 1] += 1

for _ in range(q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p, q + 1):
        for j in range(p, q + 1):
            ans += g[i - 1][j - 1]
    print(ans)


### FIXED CODE ###

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

x = [[0 for j in range(N + 1)] for i in range(N + 1)]

for _ in range(M):
    L, R = map(int, input().split())
    x[N - L][R] += 1

for i in range(1, N + 1):
    for j in range(1, N + 1):
        x[i][j] += x[i][j - 1]

for j in range(1, N + 1):
    for i in range(1, N + 1):
        x[i][j] += x[i - 1][j]

for _ in range(Q):
    p, q = map(int, input().split())
    print(x[N - p][q])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    vn = vk = vn_k = 1
    for i in range(1, n+1):
        vn = vn * i % modp
        if i == k:
            vk = vn
        if i == n-k:
            vn_k = vn
    return vn * get_inv(vk, modp) * get_inv(vn_k, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

def main():
    N,K = mis()
    import numpy as np
    p = np.array(lmis())
    o = np.ones((K,))
    print(np.max(np.convolve(p, o, mode='valid')+K)/2)


main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    vn = vk = vn_k = 1
    for i in range(1, n+1):
        vn = vn * i % modp
        if i == k:
            vk = vn
        if i == n-k:
            vn_k = vn
    return vn * get_inv(vk, modp) * get_inv(vn_k, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

def main():
    N, K = mis()
    A = lmis()
    tmp = sum(A[:K])
    tmp_max = tmp
    for i in range(K, N):
        tmp += A[i] - A[i-K]
        tmp_max = max(tmp_max, tmp)
    print((tmp_max+K)/2)


main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
N,M = map(int,input().split())
ALL = [i for i in range(N)]
ALL = set(ALL)
Graph = [[] for _ in range(N)]
gyaku = [set([]) for _ in range(N)]
for i in range(N-1+M):
  a,b = map(int,input().split())
  a-=1;b-=1
  Graph[a].append(b)
  gyaku[b].add(a)
  ALL.discard(b)
#print(Graph,gyaku)
ALL = list(ALL);root = ALL[0]

used = set([])
TS = []
def dfs(v):
  if v in used:
    return
  used.add(v)
  for w in Graph[v]:
    if w in used:
      continue
    dfs(w)
    TS.append(w)
    
dfs(root)
TS.append(root)
#TS.reverse()
#print(TS)
ans = [0 for _ in range(N)]
for i in range(N):
  now = TS[i]
  for j in range(i+1,N):
    #print(now,TS[j],gyaku[now])
    if TS[j] in gyaku[now]:
      ans[now] = TS[j]+1 #1index
      break
for x in ans:
  print(x)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N,M = map(int,input().split())
ALL = [i for i in range(N)]
ALL = set(ALL)
Graph = [[] for _ in range(N)]
gyaku = [set([]) for _ in range(N)]
for i in range(N-1+M):
  a,b = map(int,input().split())
  a-=1;b-=1
  Graph[a].append(b)
  gyaku[b].add(a)
  ALL.discard(b)
#print(Graph,gyaku)
ALL = list(ALL);root = ALL[0]

used = set([])
TS = []
def dfs(v):
  if v in used:
    return
  used.add(v)
  for w in Graph[v]:
    if w in used:
      continue
    dfs(w)
    TS.append(w)
    
dfs(root)
TS.append(root)
TS.reverse()
#print(TS)
ans = [0 for _ in range(N)]
for i in range(N):
  now = TS[i]
  for nxt in Graph[now]:
    ans[nxt] = now+1
    
for x in ans:
  print(x)
### BUGGY CODE ###

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


mod = 10 ** 9 + 7
MAX = N*M
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] % mod



def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()
ans= 0
NCK = cmb(N*M-2,K-2) 
M2 = M**2 * NCK
N2 = N**2 * NCK
for i in range(N-1):
    for j in range(i,N):
        ans += M2 * (j-i) 
        ans %= mod
        
for i in range(M-1):
    for j in range(i,M):
        ans += N2 * (j-i) 
        ans %= mod
        
print(ans)

### FIXED CODE ###

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


mod = 10 ** 9 + 7
MAX = N*M
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] % mod



def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()
ans= 0
NCK = cmb(N*M-2,K-2) 
M2 = M**2 * NCK
N2 = N**2 * NCK
for i in range(1,N):
    ans += M2 * i * (N-i)
    ans %= mod
    
for i in range(1,M):
    ans += N2 * i * (M-i)
    ans %= mod
        
print(ans)
### BUGGY CODE ###

from collections import defaultdict
N, K = map(int, input().split())

sushi_dict = defaultdict()

for i in range(N):
    t, d = map(int, input().split())
    if t in sushi_dict:
        sushi_dict[t].append(d)
    else:
        sushi_dict[t] = [d]
# print(sushi_dict)

max_array = []
for key, value in sushi_dict.items():
    value.sort()
    max_array.append((key, value[-1]))

max_array = sorted(max_array, key=lambda x: -x[1])

if K == 1:
    print(max_array[0][1] + 1)
    exit()

start_kind = min(K, len(max_array))
# print(max_array, start_kind)
ans = 0
for i in range(start_kind):
    ans += max_array[i][1]
ans += start_kind * start_kind
can_use_index = [max_array[i][0] for i in range(start_kind)]
can_use_num = []
for key, value in sushi_dict.items():
    if key not in can_use_index:
        continue
    for j in value[:-1]:
        can_use_num.append(j)

can_use_num = sorted(can_use_num,key=lambda x: -x)

use_num_count = K - start_kind
ans += sum(can_use_num[:use_num_count])
# print(can_use_num)
# print(use_num_count, start_kind)
for i in range(start_kind - 1):
    if use_num_count + i >= len(can_use_num):
        break
    ans_new = can_use_num[use_num_count + i] + (start_kind - 1 - i) * (
        start_kind - 1 - i)
    ans_old = max_array[start_kind - 1 - i][1] + (start_kind - i) * (
        start_kind - i)
    # print(ans_new, ans_old)
    if ans_new > ans_old:
        ans += (ans_new - ans_old)
    else:
        break
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
can_remove = []
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
        sushi_count[sushi[0]] = 1
    else:
        can_remove.append(sushi[1])

    # print(sushi_count)
ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

# print(ans, kiso, now_kind)
now_kind += 1

for sushi in sushi_array[add_index:]:
    if len(can_remove) == 0 or now_kind > sushi_kind:
        break
    if sushi_count[sushi[0]] == 0:
        kiso += sushi[1] - can_remove.pop()
        sushi_count[sushi[0]] = 1
        # print(ans, kiso, now_kind)
        ans = max(ans, kiso + now_kind * now_kind)
        now_kind += 1
    else:
        continue

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

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

import sys
import copy

sys.setrecursionlimit(1000000)

# input = sys.stdin.readline

# ~~~~~~~~~~~~~~~~~~~~~_(＾～＾ ｣ ∠)_~~~~~~~~~~~~~~~~~~~~~

N = int(input())

V = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = 0

for bit in range(1 << N):
    sum = 0
    for i in range(N):
        if bit & (1 << i):
            sum += V[i]
            sum -= C[i]
    ans = max(ans, sum)

print(ans)


### FIXED CODE ###

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

import sys
import copy

sys.setrecursionlimit(1000000)

# input = sys.stdin.readline

# ~~~~~~~~~~~~~~~~~~~~~_(＾～＾ ｣ ∠)_~~~~~~~~~~~~~~~~~~~~~

N = int(input())

V = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = 0
for i in range(N):
    ans += max(0, V[i] - C[i])

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

N = int(input())
L = list(map(int, input().split()))

count = 0
for i,a in enumerate(L[:N-2]):
    for j in range(i+1, N-1):
        for c in L[j+1:]:
            if abs(a-L[j]) < c < a+L[j]:
                count += 1

print(count)

### FIXED CODE ###

"""
素直に実装するとN**9
"""

import bisect
 
N = int(input())
L = list(map(int, input().split()))
 
L.sort()
ans = 0
for ai in range(N):
    for bi in range(ai+1, N):
        ci = bisect.bisect_left(L, L[ai]+L[bi])
        if ci > bi:
            ans += ci - bi - 1
        else:
            pass
 
print(ans)
### BUGGY CODE ###

# あらかじめ全ての区間における答えを求めておく
# 累積和が使える。
# p,qの値に関しての2次元座標系で考えると、値が存在するマスは限られてる
#
#
n, m, q = map(int, input().split())
ll = [[0, 0] for i in range(m)]
p = [[0, 0] for i in range(q)]
for i in range(m):
    ll[i][0], ll[i][1] = map(int, input().split())
for i in range(q):
    p[i][0], p[i][1] = map(int, input().split())
# for i in range(m):
#     print(ll[i])
# for i in range(q):
#     print(p[i])
sum = [[0 for i in range(n)] for i in range(n)]
# sum上でlをy成分＝行、rをx成分=列とする。
for j in range(m):
    y = ll[j][0]-1
    x = ll[j][1]-1
    sum[y][x] += 1
ans = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    for j in range(i, n):
        for i2 in range(i, j+1):
            for j2 in range(i, j+1):
                ans[i][j] += sum[j2][i2]

for i in range(q):
    y = p[i][0]-1
    x = p[i][1]-1
    print(ans[y][x])


### FIXED CODE ###

# あらかじめ全ての区間における答えを求めておく
# 累積和が使える。
# 2次元累積和に関しては、下記のサイトを参照。
# https://paiza.hatenablog.com/entry/2014/05/28/もし女子大生プログラマに『アルゴリズム』を図
# p,qの値に関しての2次元座標系で考えると、値が存在するマスは限られてる
#
#
n, m, q = map(int, input().split())
ll = [[0, 0] for i in range(m)]
p = [[0, 0] for i in range(q)]
for i in range(m):
    ll[i][0], ll[i][1] = map(int, input().split())
for i in range(q):
    p[i][0], p[i][1] = map(int, input().split())
# for i in range(m):
#     print(ll[i])
# for i in range(q):
#     print(p[i])
sum = [[0 for i in range(n)] for i in range(n)]
# sum上でlをy成分＝行、rをx成分=列とする。
# 各区間の値を取り込み
for j in range(m):
    x = ll[j][0]-1
    y = ll[j][1]-1
    sum[y][x] += 1
# 2次元累積和の計算
# for j in range(n):
#     print(sum[j])
# print('-'*30)
for i in range(n):
    for j in range(1, n):
        sum[i][j] += sum[i][j-1]
for i in range(n):
    for j in range(1, n):
        sum[j][i] += sum[j-1][i]
# ans = [[0 for i in range(n)] for i in range(n)]
# for i in range(n):
#    for j in range(i, n):
#        for i2 in range(i, j+1):
#            for j2 in range(i, j+1):
#                ans[i][j] += sum[j2][i2]
# for j in range(n):
#     print(sum[j])


for i in range(q):
    x = p[i][0]-1
    y = p[i][1]-1
    if x != 0:
        print(sum[y][y] - sum[y][x-1] - sum[x-1][y]+sum[x-1][x-1])
    else:
        print(sum[y][y])
### BUGGY CODE ###

n, k = map(int, input().split())
E = list(map(lambda x: (x + 1) * 0.5, list(map(int, input().split()))))
ans = sum(E[:k])
for i in range(1, n - k + 1):
    ans = max(ans, sum(E[i:i + k]))
print(ans)


### FIXED CODE ###

n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
e = [(1 + p[i]) * 0.5 for i in range(n)]
s = 0.0
for i in e[:k]:
    s += i
t = s
for i in range(n - k):
    t = t - e[i] + e[k + i]
    s = max(s, t)
print(s)
### BUGGY CODE ###

h,w = map(int, input().split())
maze = [input() for i in range(h)]
route_total = [[h*w] * w for i in range(h)]
 
black_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            black_list.append([i+1,j+1])
 
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]
 
ans = 0
stack = MyStack()
for i,black in enumerate(black_list):
    route = [[0] * w for i in range(h)]
    stack.push(black[0],black[1])
    route[black[0]-1][black[1]-1] = 0
    while len(stack.stack) > 0:
        y,x = stack.pop()
        route_num = route[y-1][x-1] + 1
        if y != h:
            if maze[y][x-1] == '.' and route[y][x-1] == 0:
                stack.push(y+1,x)
                route[y][x-1] = route_num 
                route_total[y][x-1] = min(route_num,route_total[y][x-1])
                if i == len(black_list) - 1:
                    ans = max(ans, route_total[y][x-1]) 
        if y != 1:
            if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
                stack.push(y-1,x)
                route[y-2][x-1] = route_num
                route_total[y-2][x-1] = min(route_num,route_total[y-2][x-1])
                if i == len(black_list) - 1:
                    ans = max(ans, route_total[y-2][x-1]) 
        if x != w:
            if maze[y-1][x] == '.' and route[y-1][x] == 0:
                stack.push(y,x+1)
                route[y-1][x] = route_num
                route_total[y-1][x] = min(route_num,route_total[y-1][x])
                if i == len(black_list) - 1:
                    ans = max(ans, route_total[y-1][x]) 
        if x != 1:
            if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
                stack.push(y,x-1)
                route[y-1][x-2] = route_num
                route_total[y-1][x-2] = min(route_num,route_total[y-1][x-2])
                if i == len(black_list) - 1:
                    ans = max(ans, route_total[y-1][x-2]) 

print(ans)

### FIXED CODE ###

from subprocess import call
call (('pypy3', '-c', """
from collections import deque
 
def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()
 
"""))
### BUGGY CODE ###

import numpy
 
N,K=map(int,input().split())
p=list(map(int,input().split()))
ans = 0
tmp = [0]*(N-K+1)
 
for i in range(N-K+1):
  for j in range(i,i+K):
    tmp[i]=tmp[i]+p[j]

max_index=numpy.argmax(tmp)
for i in range(max_index,max_index+K):
  for j in range(1,p[i]+1):
    ans=ans+float(j*(1/p[i]))
print(ans)

### FIXED CODE ###

import numpy
 
N,K=map(int,input().split())
p=list(map(int,input().split()))
ans = 0
tmp = [0]*(N-K+1)

for i in range(K):
  tmp[0] = tmp[0]+p[i]

for i in range(1,N-K+1):
  tmp[i]=tmp[i-1]-p[i-1]+p[i+K-1]

max_index=numpy.argmax(tmp)
for i in range(max_index,max_index+K):
  ans=ans+float(((p[i]*(p[i]+1))/2)*1/p[i])
print(ans)
### BUGGY CODE ###

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

answer=0

for i in range(1,N+1):
    f=int(A*i/B)-A*int(i/B)
    if f>answer:
        answer=f
    #print(f)
print(answer)
        

### FIXED CODE ###

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

def f(x):
    return int(A*x/B)-A*int(x/B)

print(f(min(N,B-1)))
### BUGGY CODE ###

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

b_ptn = [0] * (N)
for idx, b in enumerate(B):
  cnt = 0
  for a in A:
    if a < b:
      cnt += 1
    else:
      break
  b_ptn[idx] = cnt
ans = 0
for c in C:
  for idx, b in enumerate(B):
    if b >= c:
      break
    if idx == N-1:
      ans += b_ptn[idx]
      break
    ans += b_ptn[idx]
print(ans)


### FIXED CODE ###

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

nums = []
for idx in range(N):
  nums.append((1, A[idx]))
  nums.append((2, B[idx]))
  nums.append((3, C[idx]))
nums.sort(key=lambda x:(x[1], -x[0]))
sum_a = 0
sum_b = 0
sum_c = 0
for idx in range(3*N):
  if nums[idx][0] == 1:
    sum_a += 1
  elif nums[idx][0] == 2:
    sum_b += sum_a
  elif nums[idx][0] == 3:
    sum_c += sum_b
print(sum_c)
### BUGGY CODE ###

import bisect
import collections
import sys

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

S = readline().rstrip()
T = readline().rstrip()
if len(S) < len(T):
    S, T = T, S


def pretty(ss):
    buf = []
    while ss is not None:
        s, ss = ss
        buf.append(s)
    buf.reverse()
    return "".join(buf)


def solve():
    index = collections.defaultdict(list)
    for i, sc in enumerate(S):
        index[sc].append(i)
    dp = [None] * len(T)
    for i, tc in enumerate(T):
        if tc not in index:
            continue
        dn = list(dp)
        ii = index[tc]
        if dn[0] is None or dn[0][0] > ii[0]:
            dn[0] = (ii[0], [chr(tc), None])
        for j in range(1, len(T)):
            if dp[j - 1] is None:
                break
            k = bisect.bisect_right(ii, dp[j - 1][0])
            if k < len(ii) and (dn[j] is None or dn[j][0] > ii[k]):
                dn[j] = (ii[k], [chr(tc), dp[j - 1][1]])
        dp = dn
    for i in range(len(T) - 1, -1, -1):
        if dp[i] is not None:
            return pretty(dp[i][1])
    return ""


if __name__ == "__main__":
    print(solve())


### FIXED CODE ###

import bisect
import collections
import sys

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

S = readline().rstrip()
T = readline().rstrip()
if len(S) < len(T):
    S, T = T, S


def pretty(ss):
    buf = []
    while ss is not None:
        s, ss = ss
        buf.append(s)
    buf.reverse()
    return "".join(buf)


def solve():
    index = collections.defaultdict(list)
    for i, sc in enumerate(S):
        index[sc].append(i)
    dp = [None] * len(T)
    for i, tc in enumerate(T):
        if tc not in index:
            continue
        dn = list(dp)
        ii = index[tc]
        if dn[0] is None or dn[0][0] > ii[0]:
            dn[0] = (ii[0], [chr(tc), None])
        for j in range(1, len(T)):
            if dp[j - 1] is None:
                break
            k = bisect.bisect_right(ii, dp[j - 1][0])
            if k < len(ii) and (dn[j] is None or dn[j][0] > ii[k]):
                dn[j] = (ii[k], [chr(tc), dp[j - 1][1]])
        dp = dn
    for i in range(len(T) - 1, -1, -1):
        if dp[i] is not None:
            return pretty(dp[i][1])
    return ""


if __name__ == "__main__":
    print(solve())