def Linear_Sum(a,b,L,R): """ Sum_{i=L}^R (ai+b) を求める. """ if L<=R: return (a*(L+R)+2*b)*(R-L+1)//2 else: return 0 def Linear_Max_Sum(a,b,c,d,L,R): """ sum_{k=L}^R max(ak+b,ck+d) を求める. a,b,c,d:int L,R:int (L<=R) """ if L>R: return 0 if a==c: return Linear_Sum(a,max(b,d),L,R) if c>a: a,b,c,d=c,d,a,b if a*L+b>c*L+d: return Linear_Sum(a,b,L,R) if a*R+b