Submission #19562761

---

Source Code Expand

k = int(input())
n = int(input())
ad = [tuple(map(int, input().split())) for i in range(n)]


def calc(cost):
    count = 0
    price = 0
    for a, d in ad:
        c = 1 + (cost - a) // d
        if c > 0:
            count += c
            price += a * c + d * (c - 1) * c // 2
    return count, price


ng = 0
ok = 10 ** 11

while ok - ng > 1:
    cost = (ng + ok) // 2
    count, price = calc(cost)
    if count < k:
        ng = cost
    else:
        ok = cost

count, price = calc(ok)
print(price - ok * (count - k))

Submission Info

Judge Result