Участник:Kozlinskii/EIUASSEMBLY

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/EIUASSEMBLY/ python 3

def check_volume(M, robots, volume):
    cost = 0
    for robot in robots:
        cost += max(0, volume - robot[0]) * robot[1]
        if M < cost:
            return "not"
    if M >= cost:
        return "has"
    elif M < cost:
        return "not"
 
 
def run_one():
    s = input().split()
    N = int(s[0])
    M = int(s[1])
    robots = []
    for _ in  range(N):
        s = input().split()
        robots.append([int(s[0]), int(s[1])])
 
    l = 0
    r = 10 ** 13
    while l < r:
        m = (l + r) // 2 + 1
        val = check_volume(M, robots, m)
        if val == "not":
            r = m-1
        if val == "has":
            l = m
    return l
 
 
n = int(input())
for _ in range(n):
    print(run_one())