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: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import math
n,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
l,r=-1,10**19
while r-l>1:
    m=(l+r)//2
    b=0
    for w,d in a:
        b+=(m-w+d-1)//d
    if b<k:
        l=m
    else:
        r=m
print(r+1)

Submission status: Wrong Answer

Solution code:
import math
n,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
l,r=-1,10**19
while r-l>1:
    m=(l+r)//2
    b=0
    for w,d in a:
        b+=(m-w+d+1)//d
    if b<k:
        l=m
    else:
        r=m
print(r+1)

Submission status: Wrong Answer

Solution code:
import math
n,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
l,r=-1,10**19
while r-l>1:
    m=(l+r)//2
    b=0
    for w,d in a:
        b+=(m-w+d)//d
    if b<k:
        l=m
    else:
        r=m
print(r+1)

Submission status: Wrong Answer

Solution code:
import math
n,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
l,r=-1,10**19
while r-l>1:
    m=(l+r)//2
    b=0
    for w,d in a:
        b+=(m-w+d)//d
    if b<k:
        l=m
    else:
        r=m
print(l)

Submission status: Wrong Answer

Solution code:
import math
n,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
l,r=-1,10**19
while r-l>1:
    m=(l+r)//2
    b=0
    for w,d in a:
        b+=(m-w+d)//d
    if b<k:
        l=m
    else:
        r=m
print(r)

Submission status: Wrong Answer

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 = 1
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: Wrong Answer

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)

# print(w[0])
range_min = 0
# range_max = 2e+18
range_max = 2 * 10 ** 18

# while abs(range_max - range_min) > 1:
for x in range(150):
	mid = int((range_max + range_min) / 2)
	# print("mid: " + str(mid))

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

	#print("sum_flowers: " + str(sum_flowers))
	if sum_flowers < k:
		range_min = mid 
		#print("min: " + str(range_min) )
	else:
		range_max = mid
		#print("max: " + str(range_max) )
#print("min: " + str(range_min) )
#print("max: " + str(range_max) )
print(range_max)

Submission status: Wrong Answer

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=2*(10**18)
Low =0
for i in range(250):
    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
    elif cnt<K:
        Low = Mid
    #print(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)

Submission status: Wrong Answer

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=2*(10**18)
Low =0
for i in range(250):
    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
    elif cnt<K:
        Low = Mid
    #print(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)

Submission status: Wrong Answer

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
for i in range(200):
    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
    elif cnt<K:
        Low = Mid
    #print(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)

Submission status: Wrong Answer

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
for i in range(100):
    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
    elif cnt<K:
        Low = Mid
    #print(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)

Submission status: Wrong Answer

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**30
Low =0
for i in range(100):
    Mid=(High + Low)/2
    cnt=0
    for j in range(N):
        cnt+=max(0,1+(Mid - L[j][0])//L[j][1])
    if cnt>=K:
        High = Mid
    elif cnt<K:
        Low = Mid
    #print(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)

Submission status: Wrong Answer

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**30
Low =0
for i in range(200):
    Mid=(High + Low)/2
    cnt=0
    for j in range(N):
        cnt+=max(0,1+(Mid - L[j][0])//L[j][1])
    if cnt>=K:
        High = Mid
    elif cnt<K:
        Low = Mid
    #print(Mid)
import math
print(math.ceil(Mid))

Submission status: Wrong Answer

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: Wrong Answer

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)]
    #W = [elem[0] for elem in WD]
    #D = [elem[1] for elem in WD]

    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 = int(2*(10 ** 18)//(N-0.5))  # 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: Wrong Answer

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):
            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: Wrong Answer

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 < w:
            ma_d = d

    def is_ok(X):
        need = 0
        for i in range(N):
            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: Wrong Answer

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
            ma_d = d

    def is_ok(X):
        need = 0
        for i in range(N):
            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: Wrong Answer

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])
        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: Wrong Answer

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
        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-flag<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: Wrong Answer

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):
            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: Wrong Answer

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**19
    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: Wrong Answer

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**30
while r - l > 1:
    mid = (l + r) // 2
    flower = 0
    for w, d in wd:
        flower += (mid - w) // d + 1
        if flower >= k:
            break
    if flower >= k:
        r = mid
    else:
        l = mid
print(r)

Submission status: Wrong Answer

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:
        flower += (mid - w) // d + 1
        if flower > k:
            break
    if flower >= k:
        r = mid
    else:
        l = mid
print(r)

Submission status: Wrong Answer

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,(x - W)//D+1).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: Wrong Answer

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 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: Wrong Answer

Solution code:
def solve(l, r):
    if l > r:
        return l
    m = (l + r) // 2
    t = sum((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: Wrong Answer

Solution code:
def solve(l, r):
    if l >= r:
        return l
    m = (l + r) // 2
    t = sum((m - w) // d + 1 for w, d in flowers)
    if t < k:
        l = m + 1
    else:
        r = m
    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:
# 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**25

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

print(r)

Submission status: Time Limit Exceeded

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

High=10**30
Low =0
for i in range(300):
    Mid=(High + Low)/2
    cnt=0
    for j in range(N):
        cnt+=max(0,1+(Mid - L[j][0])//L[j][1])
    if cnt>=K:
        High = Mid
    elif cnt<K:
        Low = Mid
    #print(Mid)
import math
print(math.ceil(Mid))

Submission status: Time Limit Exceeded

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

High=10**30
Low =0
for i in range(500):
    Mid=(High + Low)/2
    cnt=0
    for j in range(N):
        cnt+=max(0,1+(Mid - L[j][0])//L[j][1])
    if cnt>=K:
        High = Mid
    elif cnt<K:
        Low = Mid
    #print(Mid)
import math
print(math.ceil(Mid))

Submission status: Time Limit Exceeded

Solution code:

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    
    N, K = map(int,input().split())
    WD = [list(map(int,input().split())) for _ in range(N)]
    #W = [elem[0] for elem in WD]
    #D = [elem[1] for elem in WD]

    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 = 4*(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: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = (int(i) for i in input().split())
    WD = [[int(i) for i in input().split()] for j in range(N)]
    W = [w[0] for w in WD]
    D = [d[1] for d in WD]

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

    def binary_search_meguru():
        ng = -1
        ok = 10**36 + 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: Time Limit Exceeded

Solution code:
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 = 10**27
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)