#include <bits/stdc++.h>
#define MAX_N (ll)23200
using namespace std;
typedef long long ll;
ll dp[1005][MAX_N+1],n;
 
struct node{
	ll w,s,v,indx;
};
node arr[100005];
bool cmp(node a,node b){
	return a.w+a.s>b.s+b.w;
}
 
ll rec(ll i,ll k){
 
	
	if(i==n+1){
		return 0;
	}
	if(dp[i][k]!=-1){
		return dp[i][k];
	}
	    ll ans=rec(i+1,k);
	    
    if(k-arr[i].w>=0){
    	ll x=min(k-arr[i].w,arr[i].s);
    	ans=max(ans,rec(i+1,x)+arr[i].v);
    }	
    
    return dp[i][k]=ans;
 
}
 
int main() {
	
	ll i,j;
	
	cin>>n;
 
	for(i=1;i<=n;i++){
			
		cin>>arr[i].w>>arr[i].s>>arr[i].v;
		arr[i].indx=i;
		
	}

	
   sort(arr+1,arr+n+1,cmp);
	
   for(i=0;i<=n;i++){
   	for(j=0;j<=MAX_N;j++){
   		dp[i][j]=-1;
   	}
   }
   
ll ans=rec(1,MAX_N);
 
cout<<ans<<endl;
	return 0;
}
### Prompt

Create a solution in cpp for the following problem:

There are N blocks, numbered 1, 2, \ldots, N. For each i (1 \leq i \leq N), Block i has a weight of w_i, a solidness of s_i and a value of v_i.

Taro has decided to build a tower by choosing some of the N blocks and stacking them vertically in some order. Here, the tower must satisfy the following condition:

* For each Block i contained in the tower, the sum of the weights of the blocks stacked above it is not greater than s_i.



Find the maximum possible sum of the values of the blocks contained in the tower.

Constraints

* All values in input are integers.
* 1 \leq N \leq 10^3
* 1 \leq w_i, s_i \leq 10^4
* 1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N
w_1 s_1 v_1
w_2 s_2 v_2
:
w_N s_N v_N


Output

Print the maximum possible sum of the values of the blocks contained in the tower.

Examples

Input

3
2 2 20
2 1 30
3 1 40


Output

50


Input

4
1 2 10
3 1 10
2 4 10
1 6 10


Output

40


Input

5
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000


Output

5000000000


Input

8
9 5 7
6 2 7
5 7 3
7 8 8
1 9 6
3 3 3
4 1 7
4 5 5


Output

22

### Response

```cpp
#include <bits/stdc++.h>
#define MAX_N (ll)23200
using namespace std;
typedef long long ll;
ll dp[1005][MAX_N+1],n;
 
struct node{
	ll w,s,v,indx;
};
node arr[100005];
bool cmp(node a,node b){
	return a.w+a.s>b.s+b.w;
}
 
ll rec(ll i,ll k){
 
	
	if(i==n+1){
		return 0;
	}
	if(dp[i][k]!=-1){
		return dp[i][k];
	}
	    ll ans=rec(i+1,k);
	    
    if(k-arr[i].w>=0){
    	ll x=min(k-arr[i].w,arr[i].s);
    	ans=max(ans,rec(i+1,x)+arr[i].v);
    }	
    
    return dp[i][k]=ans;
 
}
 
int main() {
	
	ll i,j;
	
	cin>>n;
 
	for(i=1;i<=n;i++){
			
		cin>>arr[i].w>>arr[i].s>>arr[i].v;
		arr[i].indx=i;
		
	}

	
   sort(arr+1,arr+n+1,cmp);
	
   for(i=0;i<=n;i++){
   	for(j=0;j<=MAX_N;j++){
   		dp[i][j]=-1;
   	}
   }
   
ll ans=rec(1,MAX_N);
 
cout<<ans<<endl;
	return 0;
}
```