Submission #409113

---

Source Code Expand

n = input()
hl = []
sl = []
ma = 0
hma = 0
for i in xrange(n):
    h, s = map(int, raw_input().split())
    hl.append(h)
    sl.append(s)
    hma = max(hma, h)
    ma = max(ma, h+(n-1)*s)
left = hma; right = ma+1
while True:
    mid = (left + right) / 2
    ok = True
    tl = []
    for i in xrange(n):
        if mid < hl[i]:
            ok = False
            break
        tl.append((mid - hl[i]) / sl[i])
    if ok:
        tl.sort()
        for i in xrange(n):
            if tl[i] < i:
                ok = False
                break
    if not ok:
        if left==mid:
            break
        left = mid
    else:
        right = mid
print left+1

Submission Info

Judge Result