Problem:


Score : 100 points

Problem Statement

In your garden, there is a long and narrow flowerbed that stretches infinitely to the east. You have decided to plant N kinds of flowers in this empty flowerbed. For convenience, we will call these N kinds of flowers Flower 1, 2, …, N. Also, we will call the position that is p centimeters from the west end of the flowerbed Position p.

You will plant Flower i (1 ≤ i ≤ N) as follows: first, plant one at Position w_i, then plant one every d_i centimeters endlessly toward the east. That is, Flower i will be planted at the positions w_i, w_i + d_i, w_i + 2 d_i, … Note that more than one flower may be planted at the same position.

Find the position at which the K-th flower from the west is planted. If more than one flower is planted at the same position, they are counted individually.

Constraints

1 ≤ N ≤ 10^5

1 ≤ K ≤ 10^9

1 ≤ w_i ≤ 10^{18}

1 ≤ d_i ≤ 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N K
w_1 d_1
:
w_N d_N

Output

When the K-th flower from the west is planted at Position X, print the value of X. (The westmost flower is counted as the 1-st flower.)

Sample Input 1

2 6
20 10
25 15

Sample Output 1

50

Two kinds of flowers are planted at the following positions:

Flower 1: Position 20, 30, 40, 50, 60, …

Flower 2: Position 25, 40, 55, 70, 85, …

The sixth flower from the west is the Flower 1 planted at Position 50. Note that the two flowers planted at Position 40 are counted individually.

Sample Input 2

3 9
10 10
10 10
10 10

Sample Output 2

30

Three flowers are planted at each of the positions 10, 20, 30, … Thus, the ninth flower from the west is planted at Position 30.

Sample Input 3

1 1000000000
1000000000000000000 1000000000

Sample Output 3

1999999999000000000



Sample input:
2 6
20 10
25 15


Sample output:
50

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    T = LI()
    A = LI()
    S = [-1]*N
    S[0] = T[0]; S[-1]=A[-1]
    ans = 1
    for i in range(1,N):
        if T[i]==T[i-1]:
            continue
        S[i] = T[i]
    flag = -1
    for i in range(N):
        if S[i]==A[i]:
            flag = i
            break
    if not (A[flag]==A[0] and A[flag]==T[-1]):
        print(0)
        return
    for i in range(N-1)[::-1]:
        if A[i]==A[i+1]:
            continue
        if S[i]==-1:
            S[i] = A[i]
        else:
            S[i] = max(S[i],A[i])
    #print(S)
    P = []
    pindex = []
    for i in range(N):
        if S[i]==-1:
            continue
        P.append(S[i])
        pindex.append(i)
    flag_U = True
    for i in range(len(P)-1):
        if P[i+1]>P[i]:
            if not flag_U:
                print(0)
                return
        elif P[i+1]<P[i]:
            flag_U = False
    ans = 1
    p = -1
    for i in range(N):
        if S[i]==-1:
            cur = min(P[p + 1], P[p])
            ans *= cur
            ans %= mod
        else:
            p += 1

    print(ans)
    return

def examB():
    T = I()
    A = LI()

    ans = 0
    print(ans)
    return

def examC():
    def dfs(n,s,edges,visited):
        cost = BC[s]
        now = []
        for i in edges[s]:
            if visited[i]:
                continue
            visited[i] = True
            cur,visited = dfs(n,i,edges,visited)
            now.append((cur, i))
        now.sort()
        for c,i in now:
            cost += c-now[0][0]
            children[i] = c-now[0][0]
        return cost,visited

    N, M = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        p = I()
        V[i+1].append(p)
        V[p].append(i+1)
    children = [-1]*N
    BC = defaultdict(int)
    for i in range(M):
        b, c = LI()
        BC[b] = c
    visited = [False]*N
    visited[0] = True
    ans = dfs(N,0,V,visited)
    print(children)
    print(ans)
    return

def examD():
    N, K = LI()
    W = [LI()for _ in range(N)]
    l = 0; r = inf*inf
    while(r-l>1):
        now = (l+r)//2
        cur = 0
        for i in range(N):
            cur += ((now-W[i][0])//W[i][1]+1)
        if cur<K:
            l = now
        else:
            r = now
    ans = r
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    T = LI()
    A = LI()
    S = [-1]*N
    S[0] = T[0]; S[-1]=A[-1]
    ans = 1
    for i in range(1,N):
        if T[i]==T[i-1]:
            continue
        S[i] = T[i]
    flag = -1
    for i in range(N):
        if S[i]==A[i]:
            flag = i
            break
    if not (A[flag]==A[0] and A[flag]==T[-1]):
        print(0)
        return
    for i in range(N-1)[::-1]:
        if A[i]==A[i+1]:
            continue
        if S[i]==-1:
            S[i] = A[i]
        else:
            S[i] = max(S[i],A[i])
    #print(S)
    P = []
    pindex = []
    for i in range(N):
        if S[i]==-1:
            continue
        P.append(S[i])
        pindex.append(i)
    flag_U = True
    for i in range(len(P)-1):
        if P[i+1]>P[i]:
            if not flag_U:
                print(0)
                return
        elif P[i+1]<P[i]:
            flag_U = False
    ans = 1
    p = -1
    for i in range(N):
        if S[i]==-1:
            cur = min(P[p + 1], P[p])
            ans *= cur
            ans %= mod
        else:
            p += 1

    print(ans)
    return

def examB():
    T = I()
    A = LI()

    ans = 0
    print(ans)
    return

def examC():
    def dfs(n,s,edges,visited):
        cost = BC[s]
        now = []
        for i in edges[s]:
            if visited[i]:
                continue
            visited[i] = True
            cur,visited = dfs(n,i,edges,visited)
            now.append((cur, i))
        now.sort()
        for c,i in now:
            cost += c-now[0][0]
            children[i] = c-now[0][0]
        return cost,visited

    N, M = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        p = I()
        V[i+1].append(p)
        V[p].append(i+1)
    children = [-1]*N
    BC = defaultdict(int)
    for i in range(M):
        b, c = LI()
        BC[b] = c
    visited = [False]*N
    visited[0] = True
    ans = dfs(N,0,V,visited)
    print(children)
    print(ans)
    return

def examD():
    N, K = LI()
    W = [LI()for _ in range(N)]
    l = 0; r = inf*inf
    while(r-l>1):
        now = (l+r)//2
        cur = 0
        flag = 0
        for i in range(N):
            cur += ((now-W[i][0])//W[i][1]+1)
            if (now-W[i][0])%W[i][1]==0:
                flag += 1
        if cur<K:
            l = now
        else:
            if cur-flag<K:
                l = now
            else:
                r = now
    ans = l
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,k,*t=map(int,open(0).read().split())
  *z,=zip(*[iter(t)]*2)
  ok=10**19
  ng=-1
  while ok-ng>1:
    mid=(ok+ng)//2
    if sum(max(0,0--(mid-w)//d)for w,d in z)<k:ng=mid
    else:ok=mid
  print(ng)
main()

Submission status: Time Limit Exceeded

Solution code:
n,k,*t=map(int,open(0).read().split())
*z,=zip(*[iter(t)]*2)
ok=10**20
ng=-1
while ok-ng>1:
  mid=(ok+ng)//2
  if sum(max(0,0--(mid-w)//d)for w,d in z)<k:ng=mid
  else:ok=mid
print(ng)

Submission status: Time Limit Exceeded

Solution code:
n,k,*t=map(int,open(0).read().split())
*z,=zip(*[iter(t)]*2)
ok=10**30
ng=-1
while ok-ng>1:
  mid=(ok+ng)//2
  if sum(max(0,0--(mid-w)//d)for w,d in z)<k:ng=mid
  else:ok=mid
print(ng)

Submission status: Time Limit Exceeded

Solution code:
n,k,*t=map(int,open(0).read().split())
ok=10**30
ng=-1
while ok-ng>1:
  mid=(ok+ng)//2
  if sum(max(0,0--(mid-w)//d)for w,d in zip(*[iter(t)]*2))<k:ng=mid
  else:ok=mid
print(ng)

Submission status: Time Limit Exceeded

Solution code:
def flower_number(x, a, b):
    return (x-a+b) // b

n, k = [ int(v) for v in input().split() ]
flowers = [ [ int(v) for v in input().split() ] for i in range(n) ]

ok = 10**20
ng = -1

while ok - ng > 1:
    mid = (ok+ng)//2
    if sum([ flower_number(mid, a, b) for a, b in flowers ]) >= k:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n, k = [int(item) for item in input().split()]
wd = []
for i in range(n):
    w, d = [int(item) for item in input().split()]
    wd.append((w, d))

l = -1; r = 10**20
while r - l > 1:
    mid = (l + r) // 2
    flower = 0
    for w, d in wd:
        if mid - w >= 0:
            flower += (mid - w) // d + 1
        if flower >= k:
            break
    if flower >= k:
        r = mid
    else:
        l = mid
print(r)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=[list(map(int,input().split()))for i in range(n)]
l,r=2*(10**18)+1,0
while l-r>1:
    t=(l+r)//2
    c=0
    for i,j in a:
        c+=max(0,(t-i)//j+1)
    if c<k:
        r=t
    else:
        l=t
print(l)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(n)]
ok = min(w+d*(k-1) for w,d in l)
ng = 0
while ok-ng > 1:
  mid = (ok+ng)//2
  tot = 0
  for w,d in l:
    if w > mid:
      continue
    tot += 1 + (mid-w)//d
  if tot >= k:
    ok = mid
  else:
    ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(n)]
ok = 10**29
ng = 0
while ok-ng > 1:
  mid = (ok+ng)//2
  tot = 0
  for w,d in l:
    if w > mid:
      continue
    tot += 1 + (mid-w)//d
  if tot >= k:
    ok = mid
  else:
    ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
n , k = map(int, input().strip().split(' '))

w = [0] * n
d = [0] * n
p = None
for i in range(n):
    w[i], d[i] = map(int, input().strip().split(' '))
    p1 = w[i] + (k - 1) * d[i]
    if p == None or p1 < p:
        p = p1


p1 = 1
p2 = p

def getk(p):
    kk = 0
    for i in range(n):
        if p <w[i]:
            kk += 0
        else:
            kk += (p - w[i]) // d[i] + 1
    return kk

def search(pmin, pmax):
    if pmin == pmax:
        return pmin
    else:
        mid = (pmin + pmax) // 2
        findk = getk(mid)        
        if (findk >= k):
            return search(pmin, mid)
        else:
            return search(mid+1, pmax)


print(search(p1, p2))

Submission status: Time Limit Exceeded

Solution code:
def solve(l, r):
    if l > r:
        return l
    m = (l + r) // 2
    t = sum(max(0, (m - w) // d + 1) for w, d in flowers)
    if t < k:
        l = m + 1
    else:
        r = m - 1
    return solve(l, r)


n, k = map(int, input().split())
flowers = [tuple(map(int, input().split())) for _ in range(n)]
print(solve(1, flowers[0][0] + flowers[0][1] * k))

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(x) for x in input().split()]

flowers = []

for _ in range(n):
    tmp = [int(x) for x in input().split()]
    flowers.append(tmp)

def aaa(p, l):
    count = 0
    for x in l:
        w, d = x[0], x[1]
        if p - w < 0:
            pass
        else:
            count += (p - w) // d + 1
    return count

flag = True
left, right = 1, 2 * (10 ** 18)
ans = 0

while flag:
    point = (right + left) // 2
    if point == left:
        flag = False
        if aaa(left, flowers) >= k:
            ans = left
        else:
            ans = right
    else:
        if aaa(point, flowers) < k:
            left = point
        else:
            right = point

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
kadan = [list(map(int, input().split())) for _ in range(n)]

left = 0
right = 10**18*2
while right -left > 1:
    mid = (right+left)//2
    cnt = 0
    for i in range(n):
        if mid >= kadan[i][0]:
            cnt += (mid - kadan[i][0])//kadan[i][1] + 1
    if k > cnt :
        left = mid 
    elif k <= cnt :
        right = mid 
print(right)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
WD = list(list(map(int, input().split())) for _ in range(N))

l = 0
r = 2 * 10 ** 18 + 100
while (r - l) > 1:
    pos = (r + l) // 2

    cnt = 0
    for w, d in WD:
        if pos < w:
            continue
        cnt += 1 + (pos - w) // d
    if cnt >= K:
        r = pos
    else:
        l = pos

print(r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
WD = tuple(tuple(map(int, input().split())) for _ in range(N))

l = 0
r = 2 * 10 ** 18 + 100
while (r - l) > 1:
    pos = (r + l) // 2

    cnt = 0
    for w, d in WD:
        if pos < w:
            continue
        cnt += 1 + (pos - w) // d
    if cnt >= K:
        r = pos
    else:
        l = pos

print(r)

Submission status: Accepted

Solution code:
w = []
d = []
n,k = map(int,input().split())
for i in range(n):
	w1,d1 = map(int,input().split())
	w.append(w1)
	d.append(d1)

range_min = 0
range_max = 2 * 10 ** 18

while abs(range_max - range_min) > 1:
	mid = (range_max + range_min) // 2

	sum_flowers = 0
	for i in range(n):
		if mid >= w[i]:
			sum_flowers +=  (mid - w[i]) // d[i] + 1

	if sum_flowers < k:
		range_min = mid 
	else:
		range_max = mid

print(range_max)

Submission status: Accepted

Solution code:
# Atcoder problem Solving

# Code Festival Team Relay
import math

N, K = map(int, input().split())
que = [tuple(map(int, input().split())) for _ in range(N)]


def count(X):
    cnt = 0
    for i in range(N):
        w, d = que[i]
        if X >= w:
            cnt+=(X-w)//d+1
    return cnt


# case_impossible
l = -1

# case_possible

r = 10**19

while r-l > 1:
    m = (l+r)//2
    if count(m) < K:
        l = m
    else:
        r = m

print(r)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,K=map(int,input().split())
L=[]
for i in range(N):
    s,d=map(int,input().split())
    L.append([s,d])

High=10**20
Low =0
while High - Low >1:
    Mid=(High + Low)//2
    cnt=0
    for j in range(N):
        if Mid-L[j][0]<0:
            continue
        else:
            cnt+=max(0,1+(Mid - L[j][0])//L[j][1])
    if cnt>=K:
        High = Mid
    else:
        Low = Mid
    #print(High , Low)
Mid=int(Mid)
ans=0
for j in range(N):
    ans+=max(0,1+(Mid - L[j][0])//L[j][1])
if ans>=K:
    print(Mid)
else:
    print(Mid+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
wd=[]
for i in range(n):
    wd.append(list(map(int,input().split())))
    
ok=wd[0][0]+k*wd[0][1]+2
ng=0

while ok-ng>1:
    m=(ok+ng)//2
    z=0
    for i in range(n):
        if wd[i][0]<=m:
            z+=(m-wd[i][0])//wd[i][1]+1
    if z>=k:
        ok=m
    else:
        ng=m
print(ok)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    
    N, K = map(int,input().split())
    WD = [tuple(map(int,input().split())) for _ in range(N)]

    def solve(tgt):
        res = 0
        for w,d in WD:
            res += max(0, (tgt-w)//d+1)
        if res >= K:
            return True
        else:
            return False

    ok = 2*(10 ** 18)  # exist
    ng = 0  # not exist
    while abs(ok - ng) > 1:
        cnt = (ok + ng) // 2
        if solve(cnt):
            ok = cnt
        else:
            ng = cnt
    print(ok)

Submission status: Accepted

Solution code:
import sys
def main():
  input=sys.stdin.readline
  N, K = map(int, input().split())
  wd = [tuple(map(int, input().split())) for i in range(N)]
  d = 0
  dp = [0]*N
  l = 0
  r = wd[0][0] + wd[0][1]*K
  while(r - l > 1):
    tmp = (l+r)//2
    num = 0
    for w, d in wd:
      if w <= tmp:
          num += ((tmp - w) // d) + 1
    if num >= K:
      r = tmp
    else:
      l = tmp
  print(r)
main()

Submission status: Accepted

Solution code:
import sys
def main():
  input=sys.stdin.readline
  N, K = map(int, input().split())
  wd = [tuple(map(int, input().split())) for i in range(N)]
  wd.sort()
  d = 0
  dp = [0]*N
  l = 0
  r = wd[0][0] + wd[0][1]*K
  while(r - l > 1):
    tmp = (l+r)//2
    num = 0
    for w, d in wd:
      if w <= tmp:
          num += ((tmp - w) // d) + 1
    if num >= K:
      r = tmp
    else:
      l = tmp
  print(r)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, K = (int(i) for i in input().split())
    WD = [[int(i) for i in input().split()] for j in range(N)]
    ma_w = 0
    ma_d = 0
    for w, d in WD:
        if ma_w < w:
            ma_w = w
        if ma_d < d:
            ma_d = d

    def is_ok(X):
        need = 0
        for i in range(N):
            if WD[i][0] <= X:
                need += ((X - WD[i][0]) // WD[i][1]) + 1
        if need >= K:
            return True
        else:
            return False

    def binary_search_meguru():
        ng = -1
        ok = ma_w + K * ma_d + 1
        while abs(ok - ng) > 1:
            mid = ng + (ok - ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    print(binary_search_meguru())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def examA():
    N = I()
    T = LI()
    A = LI()
    S = [-1]*N
    S[0] = T[0]; S[-1]=A[-1]
    ans = 1
    for i in range(1,N):
        if T[i]==T[i-1]:
            continue
        S[i] = T[i]
    flag = -1
    for i in range(N):
        if S[i]==A[i]:
            flag = i
            break
    if not (A[flag]==A[0] and A[flag]==T[-1]):
        print(0)
        return
    for i in range(N-1)[::-1]:
        if A[i]==A[i+1]:
            continue
        if S[i]==-1:
            S[i] = A[i]
        else:
            S[i] = max(S[i],A[i])
    #print(S)
    P = []
    pindex = []
    for i in range(N):
        if S[i]==-1:
            continue
        P.append(S[i])
        pindex.append(i)
    flag_U = True
    for i in range(len(P)-1):
        if P[i+1]>P[i]:
            if not flag_U:
                print(0)
                return
        elif P[i+1]<P[i]:
            flag_U = False
    ans = 1
    p = -1
    for i in range(N):
        if S[i]==-1:
            cur = min(P[p + 1], P[p])
            ans *= cur
            ans %= mod
        else:
            p += 1

    print(ans)
    return

def examB():
    T = I()
    A = LI()

    ans = 0
    print(ans)
    return

def examC():
    def dfs(n,s,edges,visited):
        cost = BC[s]
        now = []
        for i in edges[s]:
            if visited[i]:
                continue
            visited[i] = True
            cur,visited = dfs(n,i,edges,visited)
            now.append((cur, i))
        now.sort()
        for c,i in now:
            cost += c-now[0][0]
            children[i] = c-now[0][0]
        return cost,visited

    N, M = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        p = I()
        V[i+1].append(p)
        V[p].append(i+1)
    children = [-1]*N
    BC = defaultdict(int)
    for i in range(M):
        b, c = LI()
        BC[b] = c
    visited = [False]*N
    visited[0] = True
    ans = dfs(N,0,V,visited)
    print(children)
    print(ans)
    return

def examD():
    N, K = LI()
    W = [LI()for _ in range(N)]
    l = 0; r = 10**20
    while(r-l>1):
        now = (l+r)//2
        cur = 0
        for i in range(N):
            if now>=W[i][0]:
                cur += ((now-W[i][0])//W[i][1]+1)
        if cur<K:
            l = now
        else:
            r = now
    ans = r
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = []
for _ in range(N):
  w, d = map(int, input().split())
  a.append((w, d))

def check(x):
  res = 0
  for t in a:
    w, d = t
    res += max(0, x - w) // d + int(x >= w)
  return res >= K

ok = 10 ** 19
ng = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m
print(ok)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    F = [[int(i) for i in input().split()] for _ in range(N)]
    left, right = 0, 10 ** 20
    while right - left > 1:
        mid = (left + right) // 2
        west = 0
        for w, d in F: 
            if w <= mid: west += (mid - w) // d + 1
        if west >= K: right = mid
        else: left = mid
        #print(mid, west)
    ans = 10 ** 20
    for w, d in F:
        if w <= left: ans = min(ans, w + ((left - w)//d + 1) * d)
        else: ans = min(ans, w)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
  n,k,*t=map(int,open(0).read().split())
  *z,=zip(*[iter(t)]*2)
  ok=10**19
  ng=-1
  while ok-ng>1:
    mid=(ok+ng)//2
    if sum((mid-w)//d+1for w,d in z if w<=mid)<k:ng=mid
    else:ok=mid
  print(ok)
main()

Submission status: Accepted

Solution code:
def count(N, x, w, d):
    cnt = 0
    for i in range(N):
        if x >= w[i]:
            cnt += (x - w[i]) // d[i] + 1
    return cnt


def main():
    N, K = map(int, input().split())
    w = [0] * N
    d = [0] * N
    for i in range(N):
        w[i], d[i] = map(int, input().split())
    lo = 0
    hi = max(w) + max(d) * (K-1)
    while lo < hi:
        mid = (lo + hi) // 2
        if count(N, mid, w, d) < K:
            lo = mid + 1
        else:
            hi = mid
    print(lo)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, k = LI()


left = 0
right = 2 * 10 ** 18
L = LIR(n)
while left <= right:
    mid = (left + right) // 2
    flag = False
    ret = 0
    for w, d in L:
        if w == mid:
            ret += 1
        elif w < mid:
            ret += 1
            ret += (mid - w) // d
    if ret >= k:
        flag = True
        right = mid - 1
    else:
        flag = False
        left = mid + 1



if flag:
    print(mid)
else:
    print(mid + 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,K = map(int,input().split())
W,D = np.array([input().split() for _ in range(N)], dtype=np.int64).T

def f(x):
    # 座標xまでに生える花の個数を数える。x inclusive
    return np.maximum(0,np.minimum((x - W)//D+1,10**10)).sum()

left = 0 # K本未満
right = (1<<63)-1 # K本以上
while right > left + 1:
    mid = (left + right)//2
    if f(mid) >= K:
        right = mid
    else:
        left = mid

answer = right
print(answer)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
wds = [tuple(map(int, input().split())) for _ in range(N)]

def isOK(mid):
    num = sum([(mid-w)//d+1 if w <= mid else 0 for w, d in wds])
    return num >= K

ng, ok = 0, 2 * 10**18
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
n , k = map(int, input().strip().split(' '))

w = [0] * n
d = [0] * n
p = None
for i in range(n):
    w[i], d[i] = map(int, input().strip().split(' '))
    p1 = w[i] + (k - 1) * d[i]
    if p == None or p1 < p:
        p = p1


p1 = 1
p2 = p

def getk(p):
    kk = 0
    for i in range(n):
        if p <w[i]:
            kk += 0
        else:
            kk += (p - w[i]) // d[i] + 1
        if kk > k:
            return kk
    return kk

def search(pmin, pmax):
    if pmin == pmax:
        return pmin
    else:
        mid = (pmin + pmax) // 2
        findk = getk(mid)
        if (findk >= k):
            return search(pmin, mid)
        else:
            return search(mid+1, pmax)


print(search(p1, p2))

Submission status: Accepted

Solution code:
from bisect import bisect


def solve(l, r):
    if l > r:
        return l
    m = (l + r) // 2
    j = bisect(flowers, (m, float('inf')))
    t = sum((m - w) // d + 1 for w, d in flowers[:j])
    if t < k:
        l = m + 1
    else:
        r = m - 1
    return solve(l, r)


n, k = map(int, input().split())
flowers = [tuple(map(int, input().split())) for _ in range(n)]
flowers.sort()
print(solve(1, flowers[0][0] + flowers[0][1] * k))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = [list(map(int, input().split())) for i in range(N)]
left = 0; right = 2*10**18+1
while left+1 < right:
    mid = (left + right) // 2
    cnt = 0
    for w, d in P:
        if w <= mid:
            cnt += 1 + (mid - w) // d
    if cnt < K:
        left = mid
    else:
        right = mid
print(right)

Submission status: Accepted

Solution code:
N,K = map(int,raw_input().split())
src = []
for i in range(N):
  w,d = map(int,raw_input().split())
  src.append((w,d))
src.sort()

def enough(x):
  total = 0
  for w,d in src:
    if w > x: break
    total += (x-w)//d + 1
    if total >= K: return True
  return False

l = 0
r = 10**30
while r-l > 1:
  m = (l+r) // 2
  if enough(m):
    r = m
  else:
    l = m
print(r)

Submission status: Accepted

Solution code:
n, k = [int(x) for x in input().split()]

flowers = []

for _ in range(n):
    tmp = [int(x) for x in input().split()]
    flowers.append(tmp)

def aaa(p, l):
    count = 0
    for x in l:
        w, d = x[0], x[1]
        if p - w < 0:
            pass
        else:
            count += (p - w) // d + 1
    return count

flag = True
left, right = 1, 10 ** 19
ans = 0

while flag:
    point = (right + left) // 2
    if point == left:
        flag = False
        if aaa(left, flowers) >= k:
            ans = left
        else:
            ans = right
    else:
        if aaa(point, flowers) < k:
            left = point
        else:
            right = point

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, raw_input().split())
W = [i for i in xrange(N)]
D = [i for i in xrange(N)]
for i in xrange(N):
    W[i], D[i] = map(int, raw_input().split())

hi = 10**20
lo = 0

while hi - lo > 1:
    mid = (hi + lo) / 2
    cnt = 0
    for i in xrange(N):
        if mid >= W[i]:
            cnt += (mid-W[i])/D[i]+1
    if cnt >= K:
        hi = mid
    else:
        lo = mid
print hi

Submission status: Runtime Error

Solution code:
import sys
def main():
  N, K = map(int, input().split())
  input = sys.stdin.readline
  wd = [tuple(map(int, input().split())) for i in range(N)]
  wd.sort()
  d = 0
  dp = [0]*N
  l = 0
  r = wd[0][0] + wd[0][1]*K
  while(r - l > 1):
    tmp = (l+r)//2
    num = 0
    for w, d in wd:
      if w <= tmp:
          num += ((tmp - w) // d) + 1
    if num >= K:
      r = tmp
    else:
      l = tmp
  print(r)
main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
#define INF (1LL << 62)
using namespace std;
typedef long long ll;

ll N, K, W[100000], D[100000];

bool ok(ll x) {
  ll s = 0;
  REP(i, 0, N) if(x - W[i] >= 0) s += (x - W[i]) / D[i] + 1;
  return s >= K;
}

int main(void) {
  cin >> N >> K;
  REP(i, 0, N) cin >> W[i] >> D[i];

  ll l = 0, h = INF;
  while(l + 1 < h) {
    ll m = (l + h) / 2;
    if(ok(m)) h = m;
    else l = m;
  }
  cout << h << endl;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
#define INF (1LL << 62)
using namespace std;
typedef long long ll;

ll N, K;
vector<ll> W, D;

bool ok(ll x) {
  ll s = 0;
  REP(i, 0, N) if(x - W[i] >= 0) s += (x - W[i]) / D[i] + 1;
  return s >= K;
}

int main(void) {
  cin >> N >> K;
  W.resize(N);
  D.resize(N);
  REP(i, 0, N) cin >> W[i] >> D[i];

  ll l = 0, h = INF;
  while(l + 1 < h) {
    ll m = (l + h) / 2;
    if(ok(m)) h = m;
    else l = m;
  }
  cout << h << endl;
}