I found an interesting problem on https://codeforces.com/problemset/problem/1322/D:
A popular reality show is recruiting a new cast for the third season! $n$ candidates numbered from $1$ to $n$ have been interviewed. The candidate $i$ has aggressiveness level $l_i$, and recruiting this candidate will cost the show $s_i$ roubles.

The show host reviewes applications of all candidates from $i=1$ to $i=n$ by increasing of their indices, and for each of them she decides whether to recruit this candidate or not. If aggressiveness level of the candidate $i$ is strictly higher than that of any already accepted candidates, then the candidate $i$ will definitely be rejected. Otherwise the host may accept or reject this candidate at her own discretion. The host wants to choose the cast so that to maximize the total profit.

The show makes revenue as follows. For each aggressiveness level $v$ a corresponding profitability value $c_v$ is specified, which can be positive as well as negative. All recruited participants enter the stage one by one by increasing of their indices. When the participant $i$ enters the stage, events proceed as follows:

  The show makes $c_{l_i}$ roubles, where $l_i$ is initial aggressiveness level of the participant $i$.  If there are two participants with the same aggressiveness level on stage, they immediately start a fight. The outcome of this is:

  the defeated participant is hospitalized and leaves the show.  aggressiveness level of the victorious participant is increased by one, and the show makes $c_t$ roubles, where $t$ is the new aggressiveness level. 

 The fights continue until all participants on stage have distinct aggressiveness levels. 

It is allowed to select an empty set of participants (to choose neither of the candidates).

The host wants to recruit the cast so that the total profit is maximized. The profit is calculated as the total revenue from the events on stage, less the total expenses to recruit all accepted participants (that is, their total $s_i$). Help the host to make the show as profitable as possible.


-----Input-----

The first line contains...

I tried it in Python, but could not do it. Can you solve it?
import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
A=list(map(int,input().split()))
C=list(map(int,input().split()))
P=list(map(int,input().split()))

DP=[[-1<<30]*(n+1) for i in range(5001)]
# DP[k][cnt] = Aのmaxがkで, そういう人間がcnt人いるときのprofitの最大値

for i in range(5001):
    DP[i][0]=0

for i in range(n-1,-1,-1):
    a,c = A[i]-1,C[i]

    for j in range(n,-1,-1):
        if DP[a][j]==-1<<30:
            continue
        
        if DP[a][j] - c + P[a] > DP[a][j+1]:
            DP[a][j+1] = DP[a][j] - c + P[a]

            x, w=a, j+1
            while x+1<n+m:
                if DP[x+1][w//2] < DP[x][w] + w//2 * P[x+1]:
                    DP[x+1][w//2] = DP[x][w] + w//2 * P[x+1]

                    x,w=x+1,w//2
                else:
                    break

ANS=0
for i in range(5001):
    ANS=max(ANS,DP[i][0],DP[i][1])

print(ANS)