-----INOI 2017, Problem 2, Training-----
Ash and his Pokemon Pikachu are going on a journey.  Ash has planned his route
for the journey so that it passes through N cities, numbered 1, 2, …, N, and in this order.

When they set out, Pikachu has an initial strength of Sin as well as an experience
value (XV) of 0. As they travel they may increase his strength and experience value
in a manner to be described below.

In each city,  Ash can choose either to train Pikachu or let Pikachu battle the
Gym-leader (but not both).  The Gym-leader in ith city has experience E[i]. If
Pikachu enters a city i with strength S and decides to train, then this
increases his strength by the cube of the sum of the digits in his current
strength. For example, if he entered a city with a strength of 12, then
training will increase his strength to 12 + (1+2)3 = 39.  On the other hand,
if he enters city i with strength S and battles the Gym-leader, then this
increases his experience value XV by S*E[i].

Ash wants your help to find out the maximum XV that Pikachu can attain 
at the end of his journey.

-----Input-----
- The first line contains two space separated integers, N and Sin, which are the number of cities, and the initial strength, respectively.

- The second line contains N space separated integers, which correspond to E[1], E[2],..., E[N].

-----Output-----
- A single integer which is the maximum XV that Pikachu can attain.

-----Constraints-----
For all test cases you may assume that: 

- 1 ≤ N ≤ 5000
- 0 ≤ Sin ≤ 109
- 0 ≤ E[i] ≤ 104

Subtask 1: For 10% of the score,

- N ≤ 20 and Sin = 1

Subtask 2: For further 40% of the score,

- E[i] = k for all i
i.e. E[i] is some constant k, for all i

Subtask 3: For further 50% of the score,

- 
No further constraints.


-----Example-----
Input 1:
2 12
5 10

Output 1:
390

-----Explanation 1-----
Suppose Pikachu trains in the first city, his strength will increase to 39, because as explained above, 12 + (1+2)3 = 39. If he battles in the first city, his XV will increase by (12*5) = 60.

If Pikachu trains in the first city, and then battles in the second city, his XV will increase by 39*10 = 390. So, the final XV will be 0+390 = 390. You can check that you cannot do better than this. Hence the answer is 390.

Input 2:
4 1
100 1 6 2

Output 2:
120

-----Explanation 2-----
Pikachu battles in the first city, trains in the second and third, and then battles in the fourth city. So his strength going into each of the four cities is (1, 1, 2, 10). And so he gains 1*100 XV from the first city and 10*2 XV from the fourth city. This gets him a total of 120 XV, and you can verify that nothing better can be done.

Note:
You may download the problem statements PDF and test cases zipped files here: http://pd.codechef.com/com/inoi/problems.zip. Please feel free to use them during the contest. 
Password for the PDF and test cases zip files: DPtrumpsGreedy2017

Difficulty: interview

Starter code:

Solutions:
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf 100000000000000
typedef long long ll;
#define mp make_pair
#define f first 
#define s second
ll xp[5005];
ll train[5005];
ll dp[5005][5005];
int n;
ll power(ll x,ll y){
    ll res=1;
    while (y){
        if (y & 1){
            res=res*x; 
        }
        x=x*x;
        y=y>>1;
    }
    return res;
}
ll cube(ll x){
    ll res=x,sum=0;
    while(x!=0){
        sum+=(x%10);
        x=x/10;
    }
    res+=power(sum,3);
    return res;
}
ll max_xp(int i,int r){
    if(i>n){
        return 0;
    }
    if(dp[i][r]!=-1){
        return dp[i][r];
    }
    ll maxi=0;
    if(r<=n){
        maxi=max_xp(i+1,r+1);
    }
    maxi=max(maxi,max_xp(i+1,r)+xp[i]*train[r]);
    return dp[i][r]=maxi;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll s;
	cin>>n>>s;
	for(int i=1;i<=n;i++){
	    cin>>xp[i];
	}
	memset(dp,-1,sizeof(dp));
	train[0]=s;
	for(int i=1;i<=n;i++){
	    train[i]=cube(train[i-1]);
	}
	cout<<max_xp(1,0)<<"\n";
	return 0;
}

# include <iostream>
# include <bits/stdc++.h>
# include <cmath>
using namespace std;
vector<long long> adj[200001];
//bool vis[200001];
/*void dfs (long long s)
{
	vis[s]=true;
	for (long long next : adj[s])
	{
		if (!vis[next])
		{
			dfs(next);
		}
	}
}*/
/*long long bfs(long long s) 
{
    queue<long long> q;
    vector<bool> vis(n);
    long long c = 0;
    vis[s] = true;
    q.push(s);
    while (!q.empty())
	{
        long long currnode = q.front();
        q.pop();
        for (auto next : adj[currnode]) 
		{
            if (!vis[next]) 
			{
                vis[next] = true;
                q.push(next);
            }
        }              
        c++;
    }
    return c;
}*/
long long sdg(long long n)
{
	long long tot=0;
	while (n!=0)
	{
		tot+=n%10;
		n=n/10;
	}
	return tot;
}
long long maxy(long long a, long long b, long long c)
{
	long long arr[3]={a,b,c};
	long long ret_val=*max_element(arr,arr+3);
	return ret_val;
}
int main()
{
	//freopen("time.in","r",stdin); 
	//freopen("time.out","w",stdout);
	
	long long n;
	long long ini_str;
	cin >> n  >> ini_str;
	long long ex[n+1];
	ex[0]=0;
	for (long long i=1;i<=n;i++)
	{
		cin >> ex[i];
	}
	long long str_train[n+1];
	str_train[0]=ini_str;
	for (long long i=1;i<=n;i++)
	{
		long long temp_1=sdg(str_train[i-1]);
		str_train[i]=str_train[i-1]+pow(temp_1,3);
		//cout << i << " " << str_train[i] << endl;
		
	}
	long long dp[n+1][n+1];
	for (long long i=0;i<=n;i++)
	{
		for (long long j=0;j<=n;j++)
		{
			dp[i][j]=0;
		}
	}
	for (long long i=1;i<=n;i++)
	{
		for (long long j=1;j<=i;j++)
		{
			
			// ith city with j trains
			dp[i][j]=max(dp[i-1][j-1],(dp[i-1][j]+(str_train[j-1]*ex[i])));
			//cout << i << " " << j << " " << dp[i][j] << endl;
			
		}
	}
	long long finans=-1e9;
	for (long long i=1;i<=n;i++)
	{
		finans=max(finans,dp[n][i]);
	}
	cout << finans << endl;
	
	// OneDrive\Desktop\rand
	
}												

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)

ll n, s;
ll e[5004];
ll tval[5004];
ll dp[5004][5004];

ll increased(ll s) {
    ll s2 = s;
    int digSum = 0;
    while (s > 0) {
        digSum += s % 10;
        s /= 10;
    }
    return s2 + (ll)pow(digSum, 3);
}

ll f(int t, int i) {  // curr strength, no of times pikachu has been trained
    if (i == n) {
        return 0LL;
    }
    if (dp[t][i] > -1) {
        return dp[t][i];
    }
    return dp[t][i] = max( f(t+1, i+1) , f(t, i+1) + tval[t]*e[i]);
}

int main() {
    
    fastIO;
    
    cin >> n >> s;
    for (int i=0; i<n; i++) {
        cin >> e[i];
    }
    
    memset(dp, -1, sizeof(dp));
    
    tval[0] = s;
    for (int i=1; i <= n; i++) {
        tval[i] = increased(tval[i-1]); 
    }
    
    ll ans = f(0, 0);
    cout << ans;
    
	return 0;
}


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)

ll n, s;
ll e[5004];
ll tval[5004];
int mp[5004][5004];

ll increased(ll s) {
    int s2 = s;
    int digSum = 0;
    while (s > 0) {
        digSum += s % 10;
        s /= 10;
    }
    return s2 + (ll)pow(digSum, 3);
}

ll f(int t, int i) {  // curr strength, no of times pikachu has been trained
    if (i == n) {
        return 0;
    }
    if (mp[t][i]) {
        return mp[t][i];
    }
    return mp[t][i] = max( f(t+1, i+1) , f(t, i+1) + tval[t]*e[i]);
}

int main() {
    
    fastIO;
    
    cin >> n >> s;
    for (int i=0; i<n; i++) {
        cin >> e[i];
    }
    
    tval[0] = s;
    for (int i=1; i <= n; i++) {
        tval[i] = increased(tval[i-1]); 
    }
    
    ll ans = f(0, 0);
    cout << ans;
    
	return 0;
}


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)

ll n, s;
ll e[5000];
map<pair<ll, ll>, ll> mp;

ll increased(ll s) {
    int s2 = s;
    int digSum = 0;
    while (s > 0) {
        digSum += s % 10;
        s /= 10;
    }
    return s2 + (ll)pow(digSum, 3);
}

ll f(ll s, int i) {
    if (i == n) {
        return 0LL;
    }
    ll temp = mp[{s, i}];
    if (temp) {
        return temp;
    }
    return mp[{s, i}] = max( f(increased(s), i+1) , f(s, i+1)+s*e[i]);
}

int main() {
    
    fastIO;
    
    cin >> n >> s;
    for (int i=0; i<n; i++) {
        cin >> e[i];
    }
    
    ll ans = f(s, 0);
    cout << ans;
    
	return 0;
}


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)

ll n, s;
ll e[5000];

ll increased(ll s) {
    int s2 = s;
    int digSum = 0;
    while (s > 0) {
        digSum += s % 10;
        s /= 10;
    }
    return s2 + (ll)pow(digSum, 3);
}

ll f(ll s, int i) {
    if (i == n) {
        return 0LL;
    }
    return max( f(increased(s), i+1) , f(s, i+1)+s*e[i]);
}

int main() {
    
    fastIO;
    
    cin >> n >> s;
    for (int i=0; i<n; i++) {
        cin >> e[i];
    }
    
    ll ans = f(s, 0);
    cout << ans;
    
	return 0;
}


# include <iostream>
# include <bits/stdc++.h>
# include <cmath>
using namespace std;
vector<long long> adj[200001];
//bool vis[200001];
/*void dfs (long long s)
{
	vis[s]=true;
	for (long long next : adj[s])
	{
		if (!vis[next])
		{
			dfs(next);
		}
	}
}*/
/*long long bfs(long long s) 
{
    queue<long long> q;
    vector<bool> vis(n);
    long long c = 0;
    vis[s] = true;
    q.push(s);
    while (!q.empty())
	{
        long long currnode = q.front();
        q.pop();
        for (auto next : adj[currnode]) 
		{
            if (!vis[next]) 
			{
                vis[next] = true;
                q.push(next);
            }
        }              
        c++;
    }
    return c;
}*/
long long sdg(long long n)
{
	long long tot=0;
	while (n!=0)
	{
		tot+=n%10;
		n=n/10;
	}
	return tot;
}
vector<string> actions={"train", "fight"};
vector<long long> ex;
vector<long long> all_ans;
long long finans=-1e9;
void bfs(long long totcity,long long city, long long st, long long exp)
{
	queue<tuple<long long, long long , long long> > q;
	q.push({city,st,exp});
	bool vis1[100000]={false};
	bool vis2[100000]={false};
	bool stopwhile=false;
	while (!q.empty())
	{
		//cout << "still going " << q.size() << endl;
		tuple<long long , long long, long long> curr_tuple=q.front();
		long long curr_city=get<0>(curr_tuple);
		long long curr_str=get<1>(curr_tuple);
		long long curr_exp=get<2>(curr_tuple);
		vis1[curr_exp]=true;
		vis2[curr_str]=true;
		//finans=max(finans,curr_exp);
		q.pop();
		long long nex_str=0;
		long long nex_exp=0;
		long long nex_city=0;
		for (auto action : actions)
		{
			if (action=="train")
			{
				nex_str=curr_str+pow(sdg(curr_str),3);
				nex_exp=curr_exp;
				nex_city=curr_city+1;
			}
			else if (action=="fight")
			{
				nex_str=curr_str;
				nex_city=curr_city+1;
				nex_exp=curr_exp+(curr_str*ex[nex_city]);
			}
			//cout << action << " " << nex_city << " " << nex_str << " " << nex_exp << endl;
			bool chec=(!vis1[nex_exp] || !vis2[nex_str]);
			if ((nex_city<=totcity))
			{
				//cout << action << " " << nex_city << " " << nex_str << " " << nex_exp << endl;
				q.push({nex_city,nex_str,nex_exp});
				//vis1[nex_exp]=true;
				//vis2[nex_str]=true;
				all_ans.push_back(nex_exp);
				//finans=max(finans,nex_exp);
			}
		}
		/*if (((!vis1[nex_exp]) || (!vis2[nex_str])) && (nex_city<=totcity))
		{
			q.push({nex_city,nex_str,nex_exp});
			vis1[nex_exp]=true;
			vis2[nex_str]=true;
		}*/
	}
	
}
long long maxy(long long a, long long b, long long c)
{
	long long arr[3]={a,b,c};
	long long ret_val=*max_element(arr,arr+3);
	return ret_val;
}
int main()
{
	//freopen("time.in","r",stdin); 
	//freopen("time.out","w",stdout);
	long long n;
	long long ini_str;
	cin >> n >> ini_str;
	ex.push_back(0);
	for (long long i=1;i<=n;i++)
	{
		long long lol;
		cin >> lol;
		ex.push_back(lol);
	}
	bfs(n, 0, ini_str,0);
	cout << *max_element(all_ans.begin(),all_ans.end());
	
	// OneDrive\Desktop\rand
	
}												

// Premature optimization is the root of all evil in programming - Knuth.

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define mod (int) (1e9+7)


ll cubeSum(ll x){
	
	ll sum=0;
	
	while(x){
		ll d=x%10;
		sum+=d;
		x=x/10;
	}
	
	return sum*sum*sum;
	
}


ll dp[5005][5005];


ll recur(vector<ll> &power,ll n,ll r,ll &curr,vector<ll> &vec){
	
	if(r>n){
		return INT_MIN;
	}
	
	if(n==power.size()-1){
		return 0;
	}
	
	if(dp[n][r]!=-1){
		return dp[n][r];
	}
	
	ll val=0;
	
	val=max(val,recur(power,n+1,r+1,curr,vec));
	
	val=max(val,power[r]*vec[n]+recur(power,n+1,r,curr,vec));
	
	return dp[n][r]=val;
	
}



void solve(){
	
	ll n,s; cin>>n>>s;
	
	vector<ll> power(n+1); power[0]=s;
	
	vector<ll> vec(n);
	
	for(int i=0; i<n; i++){
		cin>>vec[i];
	}
	
	for(int i=1; i<=n; i++){
		power[i]=power[i-1]+cubeSum(power[i-1]);
		// cout<<power[i]<<" ";
	}//cout<<endl;
	
	memset(dp,-1,sizeof(dp));
	
	cout<<recur(power,0,0,s,vec)<<"\n";
	
	
	return ;
}

int main(){
    ios_base::sync_with_stdio(0);
    
    cin.tie(0);
    
    int t=1;//cin>>t;
    
    // clock_t begin, end;
    
    // double time_spent;
    
    // begin = clock(); // Time taken till now.
    
    while(t--){
    
	  solve();
        
    }
   
   //end= clock(); // Total  Time taken till now.
   
   //time_spent= (end- begin) / CLOCKS_PER_SEC; 
   
   //cout<<time_spent<<"\n";
   
   
   
	
	return 0;
}



// Premature optimization is the root of all evil in programming - Knuth.

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define mod (int) (1e9+7)


ll cubeSum(ll x){
	
	ll sum=0;
	
	while(x){
		ll d=x%10;
		sum+=d;
		x=x/10;
	}
	
	return sum*sum*sum;
	
}


ll dp[5005][5005];


ll recur(vector<ll> &power,ll n,ll r,ll &curr,vector<ll> &vec){
	
	if(r>n){
		return INT_MIN;
	}
	
	if(n==power.size()-1){
		return 0;
	}
	
	ll val=0;
	
	val=max(val,recur(power,n+1,r+1,curr,vec));
	
	val=max(val,power[r]*vec[n]+recur(power,n+1,r,curr,vec));
	
	return val;
	
}



void solve(){
	
	ll n,s; cin>>n>>s;
	
	vector<ll> power(n+1); power[0]=s;
	
	vector<ll> vec(n);
	
	for(int i=0; i<n; i++){
		cin>>vec[i];
	}
	
	for(int i=1; i<=n; i++){
		power[i]=power[i-1]+cubeSum(power[i-1]);
		// cout<<power[i]<<" ";
	}//cout<<endl;
	
	memset(dp,-1,sizeof(dp));
	
	cout<<recur(power,0,0,s,vec)<<"\n";
	
	
	return ;
}

int main(){
    ios_base::sync_with_stdio(0);
    
    cin.tie(0);
    
    int t=1;//cin>>t;
    
    // clock_t begin, end;
    
    // double time_spent;
    
    // begin = clock(); // Time taken till now.
    
    while(t--){
    
	  solve();
        
    }
   
   //end= clock(); // Total  Time taken till now.
   
   //time_spent= (end- begin) / CLOCKS_PER_SEC; 
   
   //cout<<time_spent<<"\n";
   
   
   
	
	return 0;
}



#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL_DEFINE
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#endif

ll val(ll s){
  ll sum=0;
  while(s){
    sum += s%10;
    s/=10;
  }
  return sum*sum*sum;
}

void solve(){
	ll n, s; cin >> n >> s;
	vector<ll> v(n);
	for(ll i = 0; i < n; i++){
	  cin >> v[i];
	}
	/*
	  dp[ind][str] = XV
	  dp[i][str+val(str)] = dp[i-1][str]
	  dp[i][str] = dp[i-1][str] + str*v[i]
	*/
	map<pair<ll, ll>, ll> dp;
	dp.insert({{0, s}, s*v[0]});
	dp.insert({{0, s+val(s)}, 0});
	ll ans = s*v[0];
	for(auto j: dp){
			ll i = j.first.first, k = j.first.second;
	    if(i+1>n-1) break;

	    //if(dp.find({i+1, k+val(k)})==dp.end()) dp[{i+1, k+val(k)}] = 0;
			//if(dp.find({i+1, k})==dp.end()) dp[{i+1, k}] = 0;

	    dp[{i+1, k+val(k)}] = max(dp[{i+1, k+val(k)}], dp[{i, k}]);
	    dp[{i+1, k}] = max(dp[{i+1, k}], dp[{i, k}] + (k*v[i+1]));
	    ans = max(ans, max(dp[{i+1,k}], dp[{i+1,k+val(k)}]));
	}
	//}
	cout << ans << '\n';
}

int main() {
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t; t=1;// cin >> t;
	while(t--) solve();  

#ifdef LOCAL_DEFINE
	cerr << "\nTime Elapsed: " << 1.0 * clock()/CLOCKS_PER_SEC << " s.\n";
#endif
}




#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL_DEFINE
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#endif

int val(int s){
  int sum=0;
  while(s){
    sum += s%10;
    s/=10;
  }
  return sum*sum*sum;
}

void solve(){
	int n, s; cin >> n >> s;
	vector<int> v(n);
	for(int i = 0; i < n; i++){
	  cin >> v[i];
	}
	/*
	  dp[ind][str] = XV
	  dp[i][str+val(str)] = dp[i-1][str]
	  dp[i][str] = dp[i-1][str] + str*v[i]
	*/
	map<pair<int, int>, int> dp;
	dp.insert({{0, s}, s*v[0]});
	dp.insert({{0, s+val(s)}, 0});
	//cerr << s+val(s) << '\n';
	int ans = s*v[0];
	//for(int o = 1; o < n; o++){
	for(auto j: dp){
			int i = j.first.first, k = j.first.second;
	    if(i+1>n-1) break;

	    //if(dp.find({i+1, k+val(k)})==dp.end()) dp[{i+1, k+val(k)}] = 0;
			//if(dp.find({i+1, k})==dp.end()) dp[{i+1, k}] = 0;

	    dp[{i+1, k+val(k)}] = max(dp[{i+1, k+val(k)}], dp[{i, k}]);
	    dp[{i+1, k}] = max(dp[{i+1, k}], dp[{i, k}] + (k*v[i+1]));
	    //cerr << i << ' ' << dp[{i, k}] + (k*v[i]) << '\n';
	    ans = max(ans, max(dp[{i+1,k}], dp[{i+1,k+val(k)}]));
	}
	//}
	cout << ans << '\n';
}

int main() {
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t; t=1;// cin >> t;
	while(t--) solve();  

#ifdef LOCAL_DEFINE
	cerr << "\nTime Elapsed: " << 1.0 * clock()/CLOCKS_PER_SEC << " s.\n";
#endif
}




#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL_DEFINE
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#endif

int val(int s){
  int sum=0;
  while(s){
    sum += s%10;
    s/=10;
  }
  return sum*sum*sum;
}

void solve(){
	int n, s; cin >> n >> s;
	vector<int> v(n);
	for(int i = 0; i < n; i++){
	  cin >> v[i];
	}
	/*
	  dp[ind][str] = XV
	  dp[i][str+val(str)] = dp[i-1][str]
	  dp[i][str] = dp[i-1][str] + str*v[i]
	*/
	map<pair<int, int>, int> dp;
	dp.insert({{0, s}, s*v[0]});
	dp.insert({{0, s+val(s)}, 0});
	//cerr << s+val(s) << '\n';
	int ans = s*v[0];
	//for(int o = 1; o < n; o++){
	for(auto j: dp){
			int i = j.first.first, k = j.first.second;
	    if(i+1>n-1) break;

	    if(dp.find({i+1, k+val(k)})==dp.end()) dp[{i+1, k+val(k)}] = 0;
			if(dp.find({i+1, k})==dp.end()) dp[{i+1, k}] = 0;

	    dp[{i+1, k+val(k)}] = max(dp[{i+1, k+val(k)}], dp[{i, k}]);
	    dp[{i+1, k}] = max(dp[{i+1, k}], dp[{i, k}] + (k*v[i+1]));
	    //cerr << i << ' ' << dp[{i, k}] + (k*v[i]) << '\n';
	    ans = max(ans, max(dp[{i+1,k}], dp[{i+1,k+val(k)}]));
	}
	//}
	cout << ans << '\n';
}

int main() {
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t; t=1;// cin >> t;
	while(t--) solve();  

#ifdef LOCAL_DEFINE
	cerr << "\nTime Elapsed: " << 1.0 * clock()/CLOCKS_PER_SEC << " s.\n";
#endif
}




#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL_DEFINE
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#endif

int val(int s){
  int sum=0;
  while(s){
    sum += s%10;
    s/=10;
  }
  return sum*sum*sum;
}

void solve(){
	int n, s; cin >> n >> s;
	vector<int> v(n);
	for(int i = 0; i < n; i++){
	  cin >> v[i];
	}
	/*
	  dp[ind][str] = XV
	  dp[i][str+val(str)] = dp[i-1][str]
	  dp[i][str] = dp[i-1][str] + str*v[i]
	*/
	map<pair<int, int>, int> dp;
	dp.insert({{0, s}, s*v[0]});
	dp.insert({{0, s+val(s)}, 0});
	//cerr << s+val(s) << '\n';
	int ans = s*v[0];
	//for(int o = 1; o < n; o++){
	for(auto j: dp){
			int i = j.first.first, k = j.first.second;
	    if(i+1>n-1) continue;

	    if(dp.find({i+1, k+val(k)})==dp.end()) dp[{i+1, k+val(k)}] = 0;
			if(dp.find({i+1, k})==dp.end()) dp[{i+1, k}] = 0;

	    dp[{i+1, k+val(k)}] = max(dp[{i+1, k+val(k)}], dp[{i, k}]);
	    dp[{i+1, k}] = max(dp[{i+1, k}], dp[{i, k}] + (k*v[i+1]));
	    //cerr << i << ' ' << dp[{i, k}] + (k*v[i]) << '\n';
	    ans = max(ans, max(dp[{i+1,k}], dp[{i+1,k+val(k)}]));
	}
	//}
	cout << ans << '\n';
}

int main() {
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t; t=1;// cin >> t;
	while(t--) solve();  

#ifdef LOCAL_DEFINE
	cerr << "\nTime Elapsed: " << 1.0 * clock()/CLOCKS_PER_SEC << " s.\n";
#endif
}




#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL_DEFINE
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#endif

int val(int s){
  int sum=0;
  while(s){
    sum += s%10;
    s/=10;
  }
  return sum*sum*sum;
}

void solve(){
	int n, s; cin >> n >> s;
	vector<int> v(n);
	for(int i = 0; i < n; i++){
	  cin >> v[i];
	}
	/*
	  dp[ind][str] = XV
	  dp[i][str+val(str)] = dp[i-1][str]
	  dp[i][str] = dp[i-1][str] + str*v[i]
	*/
	map<pair<int, int>, int> dp;
	dp.insert({{0, s}, s*v[0]});
	dp.insert({{0, s+val(s)}, 0});
	//cerr << s+val(s) << '\n';
	int ans = s*v[0];
	for(int o = 1; o < n; o++){
	for(auto j: dp){
			int i = j.first.first, k = j.first.second;
	    if(i+1>n-1) continue;

	    if(dp.find({i+1, k+val(k)})==dp.end()) dp[{i+1, k+val(k)}] = 0;
			if(dp.find({i+1, k})==dp.end()) dp[{i+1, k}] = 0;

	    dp[{i+1, k+val(k)}] = max(dp[{i+1, k+val(k)}], dp[{i, k}]);
	    dp[{i+1, k}] = max(dp[{i+1, k}], dp[{i, k}] + (k*v[i+1]));
	    //cerr << i << ' ' << dp[{i, k}] + (k*v[i]) << '\n';
	    ans = max(ans, max(dp[{i+1,k}], dp[{i+1,k+val(k)}]));
	}
	}
	cout << ans << '\n';
}

int main() {
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t; t=1;// cin >> t;
	while(t--) solve();  

#ifdef LOCAL_DEFINE
	cerr << "\nTime Elapsed: " << 1.0 * clock()/CLOCKS_PER_SEC << " s.\n";
#endif
}




#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf 100000000000000
typedef long long ll;
#define mp make_pair
#define f first 
#define s second
int n;
ll en[5005];
ll sen[5005];
ll dp[5005][5005];
ll power(ll x,ll y){
    ll res=1;
    while (y){
        if (y & 1){
            res=res*x; 
        }
        x=x*x;
        y=y>>1;
    }
    return res;
}
ll train(ll x){
    ll res=x;
    ll sum=0;
    while(x!=0){
        sum+=(x%10);
        x=x/10;
    }
    res+=power(sum,3);
    return res;
}
ll max_exp(int i,int j){
    //cout<<i<<" "<<j<<"\n";
    if(j>i || j<0){
        return 0;
    }
    if(i<0){
        return 0;
    }
    if(dp[i][j]!=-1){
        return dp[i][j];
    }
    ll maxi=0;
    maxi=max_exp(i-1,j-1);
    maxi=max(maxi,sen[j]*en[i]+max_exp(i-1,j));
    dp[i][j]=maxi;
    return dp[i][j];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll stren;
	memset(dp,-1,sizeof(dp));
	cin>>n>>stren;
	for(int i=0;i<n;i++){
	    cin>>en[i];
	}
	sen[0]=stren;
	for(int i=1;i<n;i++){ 
	    sen[i]=train(sen[i-1]);
	}
	ll maxi=0;
	for(int i=0;i<n;i++){
	    //cout<<i<<" ";
	    maxi=max(maxi,max_exp(n-1,i));
	}
	cout<<maxi<<"\n";
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf 100000000000000
typedef long long ll;
#define mp make_pair
#define f first 
#define s second
int n;
ll en[5005];
ll power(ll x,ll y){
    ll res=1;
    while (y){
        if (y & 1){
            res=res*x; 
        }
        x=x*x;
        y=y>>1;
    }
    return res;
}
map<tuple<int,ll,ll>,ll> dp;
map<tuple<int,ll,ll>,bool> visited;
map<ll,ll> training;
ll train(ll x){
    ll res=x;
    ll sum=0;
    while(x!=0){
        sum+=(x%10);
        x=x/10;
    }
    res+=power(sum,3);
    return res;
}
ll max_exp(int i,ll s,ll xp){
    if(i==n-1){
        return xp+s*en[i];
    }
    if(visited[{i,s,xp}]){
        return dp[{i,s,xp}];
    }
    dp[{i,s,xp}]=max(max_exp(i+1,training[s],xp),max_exp(i+1,s,xp+s*en[i]));
    visited[{i,s,xp}]=true;
    return dp[{i,s,xp}];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll s;
	cin>>n>>s;
	for(int i=0;i<n;i++){
	    cin>>en[i];
	}
	ll temp=s;
	for(int i=0;i<n;i++){
	    training[temp]=train(temp);
	    temp=training[temp];
	}
	cout<<max_exp(0,s,0)<<"\n";
	return 0;
}

// Premature optimization is the root of all evil in programming - Knuth.

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define mod (int) (1e9+7)


ll digitsSumCube(ll x){
	
	ll sum=0;
	
	while(x){
		sum+=x%10;
		x=x/10;
	}
	
	sum=sum*sum*sum;
	
	return sum;
	
}


ll recur(vector<ll> &energy,ll ind,ll s,ll e){
	
	if(ind>=energy.size()){
		return e;
	}
	
	ll add=digitsSumCube(s);
	
	return max(recur(energy,ind+1,s+add,e),recur(energy,ind+1,s,e+s*energy[ind]));
	
}


void solve(){
	
	ll n,s; cin>>n>>s;
	
	vector<ll> energy(n);
	
	for(int i=0; i<n; i++){
		cin>>energy[i];
	}
	
	cout<<recur(energy,0,s,0)<<"\n";
	
	return ;
	
}




int main(){
    ios_base::sync_with_stdio(0);
    
    cin.tie(0);
    
    int t=1;//cin>>t;
    
    // clock_t begin, end;
    
    // double time_spent;
    
    // begin = clock(); // Time taken till now.
    
    while(t--){
    
	  solve();
        
    }
   
   //end= clock(); // Total  Time taken till now.
   
   //time_spent= (end- begin) / CLOCKS_PER_SEC; 
   
   //cout<<time_spent<<"\n";
   
   
   
	
	return 0;
}



#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf 100000000000000
typedef long long ll;
#define mp make_pair
#define f first 
#define s second
int n;
ll en[5005];
ll power(ll x,ll y){
    ll res=1;
    while (y){
        if (y & 1){
            res=res*x; 
        }
        x=x*x;
        y=y>>1;
    }
    return res;
}
map<tuple<int,ll,ll>,ll> dp;
map<tuple<int,ll,ll>,bool> visited;
ll train(ll x){
    ll res=x;
    ll sum=0;
    while(x!=0){
        sum+=(x%10);
        x=x/10;
    }
    res+=power(sum,3);
    return res;
}
ll max_exp(int i,ll s,ll xp){
    if(i==n-1){
        return xp+s*en[i];
    }
    if(visited[{i,s,xp}]){
        return dp[{i,s,xp}];
    }
    dp[{i,s,xp}]=max(max_exp(i+1,train(s),xp),max_exp(i+1,s,xp+s*en[i]));
    visited[{i,s,xp}]=true;
    return dp[{i,s,xp}];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll s;
	cin>>n>>s;
	for(int i=0;i<n;i++){
	    cin>>en[i];
	}
	cout<<max_exp(0,s,0)<<"\n";
	return 0;
}

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
ll experiences[5010];
ll strengths[5010];
ll dp[5010][5010];
int calc( ll x ){
    ll sum = 0;
    while( x ){
        sum += x % 10;
        x /= 10;
    }
    return sum * sum * sum;
}
int main(){
    int N; ll S;
    cin>>N>>S;
    for( int i{1} ; i <= N ; ++i ) cin>>experiences[i];
    strengths[0] = S;
    for( int i{1} ; i <= N ; ++i ) strengths[i] = calc( strengths[i - 1] ) + strengths[i - 1];
    memset(dp, 0, sizeof(dp));
    for( int i{1} ; i <= N ; ++i ) dp[0][i] = (strengths[0] * experiences[i]) + dp[0][i - 1];
    for( int i{1} ; i <= N ; ++i )
        for( int j{i + 1} ; j <= N ; ++j )
            dp[i][j] = max(dp[i - 1][j - 1], (strengths[i] * experiences[j]) + dp[i][j - 1]);
    ll output = 0;
    for( int i{0} ; i <= N ; ++i ) output = max(output, dp[i][N]);
    cout<<output;
    return 0;
}



int long
max(int long a, int long b)
{
        return a>b ? a:b;
}

int long
digcube(int long n)
{
        int long t = n;
        int sum;
        for (sum = 0; t > 0; sum += t % 10, t /= 10);
        return sum*sum*sum;
}

int
main()
{
        int n,i,j;
        int long s;
        scanf("%d %ld", &n, &s);
        int e[n];
        for(i=0;i<n;i++)
                scanf("%d", &e[i]);
        int long strength[n];
        strength[0] = s;
        int long table[n][n];
        for(i=1;i<n;i++)
                strength[i] = strength[i-1] + digcube(strength[i-1]);
        for(i=0;i<n;i++)
                table[n-1][i] = strength[i] * e[n-1];
        for(i=n-2; i>=0; i--)
        {
                for(j=0; j<=i;j++)
                        table[i][j] = max((strength[j] * e[i] + table[i+1][j]), table[i+1][j+1]);
        }
        printf("%ld", table[0][0]);
        return 0;
}
 


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
const int inf = 0x3f3f3f3f;
int mod = 1000000007;
bool remender(ll a , ll b){return a%b;}
ll arr[5005];
ll dp[5005][5005];
int n;
ll dig(ll x){
	ll res=0;
	while(x){
		res+=x%10;
		x/=10;
	}
	return res*res*res;
}

ll rec(int i , ll s , int cnt){
	if(i==n)return 0;
	if(dp[i][cnt]!=-1)return dp[i][cnt];
	return dp[i][cnt]=max(rec(i+1,s+dig(s),cnt+1),s*arr[i]+rec(i+1,s,cnt));
}

void solve(){
	ll s;
	cin>>n>>s;
	for(int i = 0; i < n; i++)cin>>arr[i];
	memset(dp,-1,sizeof dp);
	cout<<rec(0,s,1)<<"\n";
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;
	//cin >> t;
	//while(t--){
	solve();
	//}
	return 0;
}


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
const int inf = 0x3f3f3f3f;
int mod = 1000000007;
bool remender(ll a , ll b){return a%b;}
ll arr[5005];
map<pair<int,ll>,ll> m;
int n;
ll dig(ll x){
	ll res=0;
	while(x){
		res+=x%10;
		x/=10;
	}
	return res*res*res;
}

ll rec(int i , ll s){
	if(i==n)return 0;
	if(m[{i,s}]!=0)return m[{i,s}];
	return m[{i,s}]=max(rec(i+1,s+dig(s)),s*arr[i]+rec(i+1,s));
}

void solve(){
	ll s;
	cin>>n>>s;
	for(int i = 0; i < n; i++)cin>>arr[i];
	cout<<rec(0,s)<<"\n";
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;
	//cin >> t;
	//while(t--){
	solve();
	//}
	return 0;
}


#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;

const int MOD = 1e9+7;
const ll INF = 1e18;
const int MAXN = 1e6+5;

int n;
ll s, e[5005], st[5005];

ll f(ll x) {
    int d = 0;
    while(x) {
        int r = x%10;
        x /= 10;
        d += r;
    }
    return (ll) (d*d*d);
}

void precompute() {
    st[0] = s;
    for(int i=1; i<=n; i++) {
        st[i] = st[i-1] + f(st[i-1]);
    }
}

ll dp[5005][5005];

int main() {
    FASTIO

    memset(dp,-1,sizeof(dp));
    cin >> n >> s;
    for(int i=1; i<=n; i++) cin >> e[i];
    
    precompute();
    for(int j=0; j<=n; j++) dp[n][j] = st[j]*e[n];
    for(int i=n-1; i>=1; i--) {
        dp[i][n] = st[n]*e[i]+dp[i+1][n];
        for(int j=0; j<=n-1; j++) {
            dp[i][j] = max(dp[i+1][j+1], st[j]*e[i]+dp[i+1][j]);
        }
    }
    cout << dp[1][0] << "\n";
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;

const int MOD = 1e9+7;
const ll INF = 1e18;
const int MAXN = 1e6+5;

int n;
ll s, e[5005], st[5005];

ll f(ll x) {
    int d = 0;
    while(x) {
        int r = x%10;
        x /= 10;
        d += r;
    }
    return (ll) (d*d*d);
}

void precompute() {
    st[0] = s;
    for(int i=1; i<=n; i++) {
        st[i] = st[i-1] + f(st[i-1]);
    }
}

ll dp[5005][5005];
ll xv(int i, int j) {
    if(i == n) return dp[i][j] = st[j]*e[i];
    if(dp[i][j] != -1) return dp[i][j];
    
    dp[i][j] = max(xv(i+1,j+1), st[j]*e[i]+xv(i+1,j));
    return dp[i][j];
}

int main() {
    FASTIO

    memset(dp,-1,sizeof(dp));
    cin >> n >> s;
    for(int i=1; i<=n; i++) cin >> e[i];
    
    precompute();
    cout << xv(1,0) << "\n";
    
    return 0;
}

#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

typedef long long ll;
const int mod = 1e9+7;
#define int ll

void solve(int tc) {
    int n, s;
    cin >> n >> s;
    vector<int> v(n);
    for (auto &x : v) cin >> x;
    vector<int> tr(1+n);
    tr[0] = s;
    for (int i = 1; i <= n; ++i) {
        int a = tr[i-1];
        int x = 0;
        while (a) {
            x += a%10;
            a /= 10;
        }
        tr[i] = tr[i-1] + x*x*x;
    }
    vector<vector<int>> dp(n+1, vector<int>(n+1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            dp[i][j] = dp[i-1][j] + v[i-1] * tr[j];
            if (j) dp[i][j] = max(dp[i][j], dp[i-1][j-1]);
        }
    }
    cout << *max_element(all(dp[n]));
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int tc = 1;
    //cin >> tc;
    for (int i = 1; i <= tc; ++i) solve(i);
    return 0;
}