Open a restaurant

You want to open a restaurant . Now there is n There are four locations to choose from . Mr. suanti is going to choose the right place to open some restaurants . this n The two places are arranged in the same straight line . We use a sequence of integers

To represent their relative position . Due to the location , The profit of opening a restaurant will be different . We use it pi It means that mi The profit of opening a restaurant .

In order to avoid internal competition in their own restaurants , The distance between restaurants must be greater than k.

Please help you to choose a scheme with the largest total profit .

Input

2
3 11
1 2 15
10 2 30
3 16
1 2 15
10 2 30

Output

40
30

Problem solving strategies

Why can I use DP Problem solving ？
The sub problem is i Whether a restaurant is open , The profit after the current restaurant opened plus 0-i The profit of the restaurants is the total profit

State means ：f[i] The first i The profits from the opening of a restaurant
State properties ：max
State calculation ：f[i] = max(f[i], f[j] + p[i])
f[j] To satisfy m[i] - m[k] > k The biggest profit after the restaurant opened

Core code ：

for(int i = 0; i < n;i ++)
{
    
    f[i] = p[i]; //  The initial value is set to ： Only own 
    for(int j = i - 1; j >= 0; j--)
    {
    
        if(m[i] - m[j] > k)
        {
    
            f[i] = max(f[i], f[j] + p[i]);
        }
    }
}

int ans = 0;
for(int i = 0; i < n;i ++)
    ans = max(ans, f[i]);
cout << ans << endl;