#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
template < class T> struct cLtraits_identity{
using type = T;
}
;
template < class T> using cLtraits_try_make_signed =
typename conditional<
is_integral< T> :: value ,
make_signed< T> ,
cLtraits_identity< T>
> :: type ;
template < class S, class T> struct cLtraits_common_type{
using tS = typename cLtraits_try_make_signed< S> :: type ;
using tT = typename cLtraits_try_make_signed< T> :: type ;
using type = typename common_type< tS,tT> :: type ;
}
;
template < class S, class T> inline auto min_L( S a, T b)
- > typename cLtraits_common_type< S,T> :: type {
return ( typename cLtraits_common_type< S,T> :: type ) a <= ( typename cLtraits_common_type< S,T> :: type ) b ? a : b;
}
template < class S, class T> inline S chmax( S & a, T b) {
if ( a< b) {
a= b;
}
return a;
}
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
class Solution{
public :
long long mostPoints( vector< vector< int >> & A) {
int i;
int N = A.size ( ) ;
static long long dp[ 100000 + 2 ] ;
for ( i= ( 0 ) ; i< ( N+ 1 ) ; i++ ) {
dp[ i] = 0 ;
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
chmax( dp[ i+ 1 ] , dp[ i] ) ;
chmax( dp[ min_L( N, i+ A[ i] [ 1 ] + 1 ) ] , dp[ i] + A[ i] [ 0 ] ) ;
}
return dp[ N] ;
}
}
;
// cLay version 20220116-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// class Solution {
// public:
// ll mostPoints(VVI& A){
// int N = A.size();
// static ll dp[1d5+2];
// rep(i,N+1) dp[i] = 0;
// rep(i,N){
// dp[i+1] >?= dp[i];
// dp[min(N,i+A[i][1]+1)] >?= dp[i] + A[i][0];
// }
// return dp[N];
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKI3ByYWdtYSBHQ0Mgb3B0aW1pemUoInVucm9sbC1sb29wcyIpCiNwcmFnbWEgR0NDIG9wdGltaXplKCJpbmxpbmUiKQojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0ZW1wbGF0ZTxjbGFzcyBUPiBzdHJ1Y3QgY0x0cmFpdHNfaWRlbnRpdHl7CiAgdXNpbmcgdHlwZSA9IFQ7Cn0KOwp0ZW1wbGF0ZTxjbGFzcyBUPiB1c2luZyBjTHRyYWl0c190cnlfbWFrZV9zaWduZWQgPQogIHR5cGVuYW1lIGNvbmRpdGlvbmFsPAogICAgaXNfaW50ZWdyYWw8VD46OnZhbHVlLAogICAgbWFrZV9zaWduZWQ8VD4sCiAgICBjTHRyYWl0c19pZGVudGl0eTxUPgogICAgPjo6dHlwZTsKdGVtcGxhdGUgPGNsYXNzIFMsIGNsYXNzIFQ+IHN0cnVjdCBjTHRyYWl0c19jb21tb25fdHlwZXsKICB1c2luZyB0UyA9IHR5cGVuYW1lIGNMdHJhaXRzX3RyeV9tYWtlX3NpZ25lZDxTPjo6dHlwZTsKICB1c2luZyB0VCA9IHR5cGVuYW1lIGNMdHJhaXRzX3RyeV9tYWtlX3NpZ25lZDxUPjo6dHlwZTsKICB1c2luZyB0eXBlID0gdHlwZW5hbWUgY29tbW9uX3R5cGU8dFMsdFQ+Ojp0eXBlOwp9CjsKdGVtcGxhdGU8Y2xhc3MgUywgY2xhc3MgVD4gaW5saW5lIGF1dG8gbWluX0woUyBhLCBUIGIpCi0+IHR5cGVuYW1lIGNMdHJhaXRzX2NvbW1vbl90eXBlPFMsVD46OnR5cGV7CiAgcmV0dXJuICh0eXBlbmFtZSBjTHRyYWl0c19jb21tb25fdHlwZTxTLFQ+Ojp0eXBlKSBhIDw9ICh0eXBlbmFtZSBjTHRyYWl0c19jb21tb25fdHlwZTxTLFQ+Ojp0eXBlKSBiID8gYSA6IGI7Cn0KdGVtcGxhdGU8Y2xhc3MgUywgY2xhc3MgVD4gaW5saW5lIFMgY2htYXgoUyAmYSwgVCBiKXsKICBpZihhPGIpewogICAgYT1iOwogIH0KICByZXR1cm4gYTsKfQojZGVmaW5lIG1haW4gZHVtbXlfbWFpbgppbnQgbWFpbigpewogIHJldHVybiAwOwp9CiN1bmRlZiBtYWluCmNsYXNzIFNvbHV0aW9uewogIHB1YmxpYzoKICBsb25nIGxvbmcgbW9zdFBvaW50cyh2ZWN0b3I8dmVjdG9yPGludD4+JiBBKXsKICAgIGludCBpOwogICAgaW50IE4gPSBBLnNpemUoKTsKICAgIHN0YXRpYyBsb25nIGxvbmcgZHBbMTAwMDAwKzJdOwogICAgZm9yKGk9KDApO2k8KE4rMSk7aSsrKXsKICAgICAgZHBbaV0gPSAwOwogICAgfQogICAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICAgIGNobWF4KGRwW2krMV0sIGRwW2ldKTsKICAgICAgY2htYXgoZHBbbWluX0woTiwgaStBW2ldWzFdKzEpXSwgZHBbaV0gKyBBW2ldWzBdKTsKICAgIH0KICAgIHJldHVybiBkcFtOXTsKICB9Cn0KOwovLyBjTGF5IHZlcnNpb24gMjAyMjAxMTYtMQoKLy8gLS0tIG9yaWdpbmFsIGNvZGUgLS0tCi8vICNkZWZpbmUgbWFpbiBkdW1teV9tYWluCi8vIHt9Ci8vICN1bmRlZiBtYWluCi8vIAovLyBjbGFzcyBTb2x1dGlvbiB7Ci8vIHB1YmxpYzoKLy8gICBsbCBtb3N0UG9pbnRzKFZWSSYgQSl7Ci8vICAgICBpbnQgTiA9IEEuc2l6ZSgpOwovLyAgICAgc3RhdGljIGxsIGRwWzFkNSsyXTsKLy8gICAgIHJlcChpLE4rMSkgZHBbaV0gPSAwOwovLyAgICAgcmVwKGksTil7Ci8vICAgICAgIGRwW2krMV0gPj89IGRwW2ldOwovLyAgICAgICBkcFttaW4oTixpK0FbaV1bMV0rMSldID4/PSBkcFtpXSArIEFbaV1bMF07Ci8vICAgICB9Ci8vICAgICByZXR1cm4gZHBbTl07Ci8vICAgfQovLyB9Owo=