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

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):



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



l = -1



r = 10**19

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

print(r)

Solution (Python):
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
    
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)

Solution (Python):
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)

Solution (Python):
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)  
    ng = 0  
    while abs(ok - ng) > 1:
        cnt = (ok + ng) // 2
        if solve(cnt):
            ok = cnt
        else:
            ng = cnt
    print(ok)

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
import sys
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)

Solution (Python):
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])
    
    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()

"""

"""

Solution (Python):
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)

Solution (Python):
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
        
    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()

Solution (Python):
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
        
    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()

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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):
    
    return np.maximum(0,np.minimum((x - W)//D+1,10**10)).sum()

left = 0 
right = (1<<63)-1 
while right > left + 1:
    mid = (left + right)//2
    if f(mid) >= K:
        right = mid
    else:
        left = mid

answer = right
print(answer)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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