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

import itertools
import math

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)

mod = 10**9+7

# print(list(itertools.combinations(range(6), 3)))
# A = range(6)
# N = 6
# K = 3

def comb(n, k):
    if n >= k:
        return math.factorial(n) // (math.factorial(n-k) * math.factorial(k))
    else:
        return 0

ans = 0
for i in range(N):
    # print(comb(i, K-1, exact=True), comb(N-i-1, K-1, exact=True))
    ans += (comb(i, K-1) - comb(N-i-1, K-1)) * A[i] % mod

print(ans%mod)

### FIXED CODE ###

# import itertools
# import math

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)

mod = 10**9+7

# print(list(itertools.combinations(range(6), 3)))
# A = range(6)
# N = 6
# K = 3

# 二項係数を素数で割った余り
def combMod(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
    # fact = [-1 for _ in range(n+1)]
    # fact[0] = 1
    # fact[1] = 1
    # inv = [-1 for _ in range(n+1)]
    # inv[0] = 0
    # inv[1] = 1
    # factinv = [-1 for _ in range(n+1)]
    # factinv[0] = 1
    # factinv[1] = 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
p = mod
    
for i in range(2, N + 1):
    # fact[i] = ((fact[i-1] * i) % p)
    # inv[i] = ((-inv[p % i] * (p // i)) % p)
    # factinv[i] = ((factinv[i-1] * inv[i]) % p)
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)




ans = 0
for i in range(N):
    num = combMod(i, K-1, mod) % mod
    ans += num * A[i] % mod
    ans -= num * A[N-i-1] % mod
    ans %= mod

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

import itertools

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

slen = list(itertools.combinations(S, N - (N - 3)))
setlen = set(slen)

print(len(setlen))

### FIXED CODE ###


N = int(input())
S = input()
ans = 0
anslst = []
for i in range(10):
    for j in range(10):
        for k in range(10):
            anslst.append(str(i) + str(j) + str(k))

tmp = ans
for i in anslst:
    a, b, c = i
    index1 = S.find(a)
    index2 = S.find(b, index1 + 1)
    index3 = S.find(c, index2 + 1)
    if index1 != -1 and index2 != -1 and index3 != -1:
        ans += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


def solve(N, K, adj, queries):
    WHITE, GRAY, BLACK = 0, 1, 2

    num_of_nodes = N+1
    color = [WHITE] * num_of_nodes  # 各ノードの訪問状態
    d = [float('inf')] * num_of_nodes  # 始点からの重み

    # dijkstra(self, start):
    d[K] = 0
    pq = [(0, K)]

    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue

        for v, c in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heappush(pq, (d[v], v))
                color[v] = GRAY

    # 結果の表示
    for x, y in queries:
        print(d[x] + d[y])



def main():
    # データの入力
    N = int(input())
    adj = [[] for _ in range(N+1)]
    for i in range(N-1):
        f, t, c = [int(x) for x in input().split(' ')]
        adj[f].insert(0, (t, c))
        adj[t].insert(0, (f, c))

    queries = []
    Q, K = [int(x) for x in input().split(' ')]
    for i in range(Q):
        queries.append([int(x) for x in input().split(' ')])

    # 経路の探索
    solve(N, K, adj, queries)



if __name__ == '__main__':
    main()
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


# データの入力
N = int(input())
adj = [[] for _ in range(N+1)]
for i in range(N-1):
    f, t, c = [int(x) for x in input().split(' ')]
    adj[f].append((t, c))
    adj[t].append((f, c))

queries = []
Q, K = [int(x) for x in input().split(' ')]
for _ in range(Q):
    queries.append([int(x) for x in input().split(' ')])

# 経路の探索
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * (N+1)  # 各ノードの訪問状態
d = [float('inf')] * (N+1)  # 始点からの重み

# dijkstra
d[K] = 0
pq = [(0, K)]

while pq:
    cost, u = heappop(pq)
    color[u] = BLACK
    if d[u] < cost:
        continue

    for v, c in adj[u]:
        if color[v] == BLACK:
            continue
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            color[v] = GRAY

# 結果の表示
for x, y in queries:
    print(d[x] + d[y])
### BUGGY CODE ###

import math
from functools import reduce


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

    tmp = [0] * N

    s = 1
    for i in range(N):
        tmp[- i - 1] = s
        s *= A[-i - 1]

    is_pairwise_coprime = True
    for i in range(N - 1):
        if math.gcd(A[i], tmp[i]) != 1:
            is_pairwise_coprime = False

    gcd_ = reduce(math.gcd, A)

    if is_pairwise_coprime:
        print('pairwise coprime')
    elif gcd_ == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
from functools import reduce
from collections import defaultdict


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A_max = max(A)

    is_pairwise_coprime = True

    D = [-1] * (A_max + 1)
    for i in range(2, A_max + 1):
        if D[i] == -1:
            D[i] = i
            for j in range(i*i, A_max+1, i):
                D[j] = i

    def factorization(n):
        # assert 0 < n <= A_max
        primes_ = defaultdict(int)
        temp = n
        while temp > 1:
            primes_[D[temp]] += 1
            temp = temp // D[temp]

        return primes_

    P = [False]*(A_max+1)

    # primes = set({})
    for i in range(N):
        for p in factorization(A[i]).keys():
            # if p in primes:
            if P[p]:
                is_pairwise_coprime = False
                break
            else:
                # primes.add(p)
                P[p] = True

    gcd_ = reduce(math.gcd, A)

    if is_pairwise_coprime:
        print('pairwise coprime')
    elif gcd_ == 1:
        print('setwise coprime')
    else:
        print('not coprime')


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

n = int(input())
a = list(map(int, input().split()))
x = 2020202020
for i in range(1, n):
    x = min(x, abs(sum(a[:i]) - sum(a[i:])))
print(x)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
y = sum(a)
ans = 2020202020
for i in range(n - 1):
    x += a[i]
    y -= a[i]
    ans = min(ans, abs(x - y))
print(ans)
### BUGGY CODE ###

import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*n
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in edge[p].items():
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

def Dijkstra(start):
    inf = float('inf')
    d = [[inf]*(A+1) for _ in range(n)]
    d[start][min(s,A)] = 0
    pq = [(0,start,min(s,A))]
    heapq.heapify(pq)
    while pq:
        dist,p,money = heapq.heappop(pq)
        while True:
            if money >= A:
                money = A
            for to,(cost,time) in path[p].items():
                if money < cost or d[to][money - cost] <= dist + time:continue
                d[to][money - cost] = dist + time
                heapq.heappush(pq, (d[to][money - cost],to,money - cost))
            if money == A:break
            money += C[p]
            dist += D[p]
        m = inf
    return d

n,m,s = map(int,input().split())
path = [{} for _ in range(n)]
A = 0
for i in range(m):
    u,v,a,b = map(int,input().split())
    A += a
    u -= 1
    v -= 1
    path[u][v] = (a,b)
    path[v][u] = (a,b)
A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = map(int,input().split())
ans = Dijkstra(0)
for a in ans[1:]:
    print(min(a))


### FIXED CODE ###

import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*(n*(A+1))
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in edge[p].items():
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

n,m,s = map(int,input().split())
edge = [{} for _ in range(n)]
A = 2500
for i in range(m):
    u,v,a,b = map(int,input().split())
    # A += a
    u -= 1
    v -= 1
    edge[u][v] = (a,b)
    edge[v][u] = (a,b)


A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = map(int,input().split())

path = [{} for _ in range(n*(A+1))]
for i in range(n):
    for j in range(A+1):
        for to,(a,b) in edge[i].items():
            if j - a >= 0:
                path[i*(A+1)+j][to*(A+1)+j-a] = b
        path[i*(A+1)+j][i*(A+1)+min(j+C[i],A)] = D[i]

ans = Dijkstra(path,min(s,A))
for i in range(1,n):
    print(min(ans[i*(A+1):i*(A+1)+A+1]))
### BUGGY CODE ###

def fun(x):
    ret = 1
    while x:
        ret *= x
        x -= 1
    return ret

def cmb(n,r):
    if n==r: return 1
    if n<r: return 0
    else: return fun(n) // (fun(r)*fun(n-r))


n = int(input())

ss = [sorted(input()) for i in range(n)]
ss.sort()

tmp = ss[0]
cnt = 0
ans = 0
for i in range(n):
    if tmp == ss[i]: cnt+=1
    else:
        tmp = ss[i]
        ans += cmb(cnt, 2)
        cnt=1
print(ans+cmb(cnt,2))

### FIXED CODE ###

n = int(input())
d = {}

for i in range(n):
    s = "".join(sorted(input()))
    if s in d: d[s] += 1
    else: d[s] = 1
ans = 0
for i in d.values():
    ans += (i*i-i)//2
print(ans)
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    def bfs(i,j):
        que = collections.deque([[i,j,0]])
        footprint = [[-1 for _ in range(W)] for _ in range(H)]

        while len(que) >=1:
            a, b, c = que.popleft()
            footprint[a][b] = c

            if a != 0:
                if footprint[a-1][b] == -1 and grid[a-1][b] == '.':
                    que.append([a-1, b, c+1])
            if a != H-1:
                if footprint[a+1][b] == -1 and grid[a+1][b] == '.':
                    que.append([a+1, b, c+1])
            if b != 0:
                if footprint[a][b-1] == -1 and grid[a][b-1] == '.':
                    que.append([a, b-1, c+1])
            if b != W-1:
                if footprint[a][b+1] == -1 and grid[a][b+1] == '.':
                    que.append([a, b+1, c+1])

        # print(footprint)
        return max([max(item) for item in footprint])

    res = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':
                res = max(res, bfs(i,j))
            if res == H+W-2:
                break
        if res == H+W-2:
                break
    
    print(res)
        


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    res = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':

                que = deque([[i,j]])
                footprint = [[-1 for _ in range(W)] for _ in range(H)]
                footprint[i][j] = 0

                while que:
                    a, b = que.popleft()
                    c = footprint[a][b]
                    if c > res:
                        res = c

                    if a != 0 and footprint[a-1][b] == -1 and grid[a-1][b] == '.':
                        que.append([a-1, b])
                        footprint[a-1][b] = c + 1
                    if a != H-1 and footprint[a+1][b] == -1 and grid[a+1][b] == '.':
                        que.append([a+1, b])
                        footprint[a+1][b] = c + 1
                    if b != 0 and footprint[a][b-1] == -1 and grid[a][b-1] == '.':
                        que.append([a, b-1])
                        footprint[a][b-1] = c + 1
                    if b != W-1 and footprint[a][b+1] == -1 and grid[a][b+1] == '.':
                        que.append([a, b+1])
                        footprint[a][b+1] = c + 1

    print(res)
        


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

import sys
input = sys.stdin.readline
n,k=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
ab.sort()
l=[]
m=0
for i in range(len(ab)):
    for j in range(ab[i][1]):
        l.append(ab[i][0])
        m+=1
    if m>k:break
print(l[k-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,k=map(int,input().split())
l=[0]*10**5
for i in range(n):
    a,b=map(int,input().split())
    l[a-1]+=b
m=0
for i in range(10**5):
    if m+l[i]>=k:print(i+1);break
    else: m+=l[i]
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
idx = 0
s=0
e=0

for i in range(n-k+1):
    s1 = sum(p[i:i+k])
    if s1 > s:
        idx = i
        s = s1

l = [(1 + p1)*(p1//2 + 0.5*(p1%2))/p1 for p1 in p[idx:idx+k]]

print(sum(l))


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
l=[sum(p[:k])]

for i in range(n-k):
    l1=l[i] - p[i] + p[i+k]
    l.append(l1)

print((max(l)+k)/2)
### BUGGY CODE ###

if __name__ == '__main__':
    n = int(input())
    p = list(map(int, input().split(" ")))

    count = 0
    for i in range(n):
        flag = 0
        for j in range(n):
            if i > j:
                if p[i] > p[j]:
                    flag = 1
                    # print(i, j)
        if flag == 0:
            count = count + 1

    print(count)

### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    p = list(map(int, input().split(" ")))

    count = 0
    min_num = 10000000
    for i in p:
        if i < min_num:
            count = count + 1
            min_num = i

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

from operator import itemgetter
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = []
for i in range(M):
    move.append(list(map(int, input().split())))
move.sort(key=itemgetter(0))

dp = [-1] * (N+1)

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    for x,y in move:
        if now_x == x:
            maxpath = max(maxpath,findpath(y) + 1)
        if now_x < x:
            break
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = {}
for i in range(M):
    x,y = map(int, input().split())
    move.setdefault(x,[]).append(y)

dp = [-1] * (N+10)

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    if now_x in move.keys():
        for y in move[now_x]:
            maxpath = max(maxpath,findpath(y) + 1)
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import copy

string = [x for x in input()]

concat_string = copy.copy(string)
count = 0
while True:
    num_delete = 0
    flags_delete = [False] * len(string)
    
    i = 0
    j = 1
    not_delete_list = []
    while True:
        if j >= len(concat_string) or i < 0:
            break
        if concat_string[i] != concat_string[j]:
            flags_delete[i] = True
            flags_delete[j] = True
            num_delete += 2
            
            if i == 0:
                i = j + 1
                j = i + 1
            else:
                if len(not_delete_list) > 0:
                    i = not_delete_list[-1]
                    not_delete_list = not_delete_list[:-1]
                    j = j + 1
                else:
                    i = j + 1
                    j = i + 1
        else:
            not_delete_list.append(i)
            i = j
            j = i + 1
            
    if num_delete == 0:
        break
    
    count += num_delete
    concat_string = [concat_string[i] for i in range(len(concat_string)) if flags_delete[i] == False]

print(count)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import copy

string = [x for x in input()]

concat_string = copy.copy(string)
num_delete = 0

i = 0
j = 1
not_delete_list = []
while True:
    if j >= len(concat_string) or i < 0:
        break
    if concat_string[i] != concat_string[j]:
        num_delete += 2
        
        if i == 0:
            i = j + 1
            j = i + 1
        else:
            if len(not_delete_list) > 0:
                i = not_delete_list.pop(-1)
                j = j + 1
            else:
                i = j + 1
                j = i + 1
    else:
        not_delete_list.append(i)
        i = j
        j = i + 1


print(num_delete)
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
G = defaultdict(list)
A = list(map(int, input().split()))
A = sorted(A)
for i in range(N):
    for j in range(i + 1, N):
        for k in range(30):
            if i != j and A[i] + A[j] == 2 ** k:
                G[i].append(N + j)
                G[j].append(N + i)
                break
            if A[i] + A[j] < 2 ** k:
                break

used = [False] * 2 * N
match = [-1] * 2 * N


def dfs(v):
    global used
    used[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True


ma = 0
for i in range(N):
    if match[i] < 0:
        used = [False] * 2 * N
        if dfs(i):
            ma += 1

print(ma // 2)

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    if d[a[i]] == 0:
        continue
    for k in range(30, -1, -1):
        inv = pow2[k] - a[i]
        if inv < 0 or inv > a[i]:
            continue
        if inv != a[i]:
            if d[inv] > 0 and d[a[i]] > 0:
                p = min(d[inv], d[a[i]])
                num += p
                d[inv] -= p
                d[a[i]] -= p
                break
        else:
            if d[a[i]] >= 2:
                num += d[a[i]] // 2
                d[a[i]] %= 2
                break
print(num)
### BUGGY CODE ###

from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def find(s, t):
    global g
    queue = deque()
    queue.append((0, s))
    queue.append((1, t))
    visited = (set(), set())
    visited[0].add(s)
    visited[1].add(t)

    def remember(visited, new):
        g[new] |= visited
        for v in visited:
            g[v].add(new)
        visited.add(new)

    while queue:
        st, i = queue.popleft()
        for f in g[i]:
            if f in visited[not st]:
                return True
            if f not in visited[st]:
                remember(visited[st], f)
                queue.append((st, f))
    return False


q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if find(s, t) else 'no')
    q -= 1

### FIXED CODE ###

n, m = map(int, input().split())
g = [set() for _ in range(n)]
group_ids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, group_ids
    queue = set(g[s])
    group_ids[s] = gid

    while queue:
        i = queue.pop()
        if not group_ids[i]:
            group_ids[i] = gid
            queue.update(g[i])


gid = 1
for i in range(n):
    if group_ids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = group_ids[s], group_ids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1
### BUGGY CODE ###

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

N, Q = map(int, input().split())
E = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
visit = [False]*N
ans = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x


def dfs(v):
    if not visit[v]:
        visit[v] = True
        for nxt in E[v]:
            ans[nxt] += ans[v]
            dfs(nxt)


dfs(0)
print(*ans)


### FIXED CODE ###

from collections import defaultdict

N, Q = map(int, input().split())
E = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
ans = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

for i in range(N):
    for t in E[i]:
        ans[t] += ans[i]
print(*ans)
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()
    x = set()

    for i in range(n)[:-2]:
        for j in range(n)[i + 1:-1]:
            for k in range(n)[j + 1:]:
                item = s[i] + s[j] + s[k]
                if item not in x:
                    x.add(item)

    print(len(x))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = input()

    c = 0
    l1 = set()
    for i in range(n)[:-2]:
        if s[i] in l1:
            continue
        l1.add(s[i])
        l2 = set()
        for j in range(n)[i + 1:-1]:
            if s[j] in l2:
                continue
            l2.add(s[j])
            c += len(set(list(s[j + 1:])))

    print(c)


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

N, A, B = map(int, input().split())
ball = []
import sys
cnt = 0
while 1:
    for i in range(A):
        ball += [0]
        cnt += 1
        if len(ball)==N:
            print(cnt)
            sys.exit()
    for j in range(B):
        ball += [1]
        if len(ball)==N:
            print(cnt)
            sys.exit()

### FIXED CODE ###

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

n = N-((A+B)*kaisu)
if n >= A:
    print(A*(kaisu+1))
else:
    print(A*kaisu+n)