二分的题型，注意二分什么和结束条件

import sys

input=lambda:sys.stdin.readline().strip()

n,m=map(int,input().split())

f=[[0]*2 for i in range(n)]

for i in range(n):

    f[i][0],f[i][1]=map(int,input().split())

def check(x):

    t=0

    for i in range(n):

        u,v=f[i][0],f[i][1]

        if u<x:

            continue

        t+=(u-x)//v+1

        if t>m:

            return False

    return True

l,r=0,int(1e7) #按照使用次数是否小于等于m来分类

while l<r:

    mid=(l+r)//2

    if check(mid):

        r=mid

    else:

        l=mid+1

ans=0

t=0

for i in range(n):

    u,v=f[i][0],f[i][1]

    if u<l:

        continue

    w=(u-l)//v+1

    t+=w

    ans+=(u+u-(w-1)*v)*w//2

if l!=0:

    ans+=(l-1)*(m-t)

print(ans)