Okabe needs bananas for one of his experiments for some strange reason. So he decides to go to the forest and cut banana trees.

Consider the point (x,?y) in the 2D plane such thatx andy are integers and0?≤?x,?y. There is a tree in such a point, and it hasx?+?y bananas. There are no trees nor bananas in other points. Now, Okabe draws a line with equation. Okabe can select a single rectangle with axis aligned sides with all points on or under the line and cut all the trees in all points that are inside or on the border of this rectangle and take their bananas. Okabe's rectangle can be degenerate; that is, it can be a line segment or even a point.

Help Okabe and find the maximum number of bananas he can get if he chooses the rectangle wisely.

Okabe is sure that the answer does not exceed 10¹⁸. You can trust him.

Input

The first line of input contains two space-separated integers m and b (1?≤?m?≤?1000,1?≤?b?≤?10000).

Output

Print the maximum number of bananas Okabe can get from the trees he cuts.

Example

Input 1 5 Output 30 Input 2 3 Output 25

Note

The graph above corresponds to sample test 1. The optimal rectangle is shown in red and has30 bananas.

題意： 在給出的一次函數(shù)曲線中找到下方向找到一個矩形 矩形的每一個點都大于0 權值為每個整點x+y 給定m和b 求最大的矩形
分析： 求最大的必然是整點 因為如果非整點的話不如在整點的矩形大 （可以根據(jù)圖中看出） 本題我們可以考慮暴力 如果暴力的話 我們可以只暴力一維 另一維通過函數(shù)計算得到 那么最大的x = m*b 最大的y = b 所以不如枚舉y 然后對于每一個(x,y) 可以推推公式得到權值計算的O（1）方法 復雜度O(n)
code: #include<bits/stdc++.h> using namespace std; typedef long long ll;int main() {int m,b;scanf("%d%d",&m,&b);ll ans=0;for(int y=b;y>=0;y--){int x = (b-y)*m;ans = max(ans,1LL*(1+y)*y/2*(x+1)+1LL*(1+x)*x/2*(y+1));// 里面的式子也要轉成longlong 否則WA 注意數(shù)據(jù)范圍比較大}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的CF#420 B. Okabe and Banana Trees　思维｜暴力｜几何的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。