“我有个愿望，我希望穿越一切找到你。”

这是个二维平面世界，平面上有n个特殊的果实，我从(0,0)点出发，希望得到尽量多的果实，但是出于某种特殊的原因，我的运动方式只有三种（假设当前我在(x,y)）：

1、我可以走到(x+1,y)

2、我可以走到(x,y+1)

3、我可以走到(x+1,y+1)

现在我需要你的帮助，帮我找出我最多能够得到多少个果实。

经典的二维dp，我们设f[i][j]表示。。。

非常水的一维dp，我们将所有的点按照x排序让后做一次最长不下降子序列就好了

这里比较老实地用了离散化+数据结构，比二分好想多了。。。2333333

#pragma GCC optimize("O3")#pragma G++ optimize("O3")#include
    
     #include
     
      #include
      
       #define N 100010#define mid (l+r>>1) using namespace std;struct dt{ int x,y; } s[N];int n,v[N],r[N],m,w[N<<2],f[N];inline bool c1(dt a,dt b){ return a.x