Problem:
 Score : 100 points    Problem Statement There are N flowers arranged in a row.
For each i ( 1 \leq i \leq N ), the height and the beauty of the i -th flower from the left is h_i and a_i , respectively.
Here, h_1, h_2, \ldots, h_N are all distinct.  Taro is pulling out some flowers so that the following condition is met:   The heights of the remaining flowers are monotonically increasing from left to right.   Find the maximum possible sum of the beauties of the remaining flowers.      Constraints  All values in input are integers.  1 \leq N \leq 2 × 10^5  1 \leq h_i \leq N  h_1, h_2, \ldots, h_N are all distinct.  1 \leq a_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  h_1  h_2  \ldots  h_N  a_1  a_2  \ldots  a_N       Output Print the maximum possible sum of the beauties of the remaining flowers.        Sample Input 1 4
3 1 4 2
10 20 30 40      Sample Output 1 60  We should keep the second and fourth flowers from the left.
Then, the heights would be 1, 2 from left to right, which is monotonically increasing, and the sum of the beauties would be 20 + 40 = 60 .       Sample Input 2 1
1
10      Sample Output 2 10  The condition is met already at the beginning.       Sample Input 3 5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000      Sample Output 3 5000000000  The answer may not fit into a 32-bit integer type.       Sample Input 4 9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5      Sample Output 4 31  We should keep the second, third, sixth, eighth and ninth flowers from the left.

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

class SegmentTree:
    def __init__(self, size, default, op=max):
        self.size = 2**size.bit_length()
        self.dat = [default]*(self.size*2)
        self.op = op

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

    def add(self, i, x):
        i += self.size
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b=None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        res = None
        while l < r:
            if l & 1:
                if res is None:
                    res = self.dat[l]
                else:
                    res = self.op(res, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                if res is None:
                    res = self.dat[r]
                else:
                    res = self.op(res, self.dat[r])
            l >>= 1
            r >>= 1
        return res


def solve():
    n = II()
    h = LI()
    a = LI()
    dp = SegmentTree(n + 1, 0)
    for i in range(n):
        hi, ai = h[i], a[i]
        ma = dp.get(0, hi)
        dp.update(hi, ma + ai)
    print(dp.get(0, n + 1))
    return



if __name__ == '__main__':
    solve()

Solution (Python):
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 1 << ((self.n - 1).bit_length())
        self.op = op 
        self.e = e 
        self.v = self._build(lst)
        
    def _build(self, lst):
        
        
        tree = [self.e] * (self.N - 1) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 2, -1, -1):
            tree[i] = self.op(tree[2*i + 1], tree[2*i + 2])
        return tree
    
    def __getitem__(self, i):
        return self.v[i + self.N - 1]
    
    
    def update(self, i, x):
        i += self.N - 1
        self.v[i] = x
        while i > 0:
            i -= 1; i >>= 1
            self.v[i] = self.op(self.v[2*i + 1], self.v[2*i + 2])
    
    
    def query(self, l, r):
        left = l + self.N - 1
        right = r + self.N - 1
        L = self.e; R = self.e
        while left < right:
            if left & 1 == 0: 
                L = self.op(L, self.v[left])
                left += 1
            if right & 1 == 0: 
                right -= 1
                R = self.op(self.v[right], R)
            left -= 1; left >>= 1
            right >>= 1
        return self.op(L, R)

def coord_compress(A):
    B = {a: i for i, a in enumerate(sorted(set(A)))}
    return [B[a] for a in A]
    
N = int(input())
*H, = map(int, input().split())
*A, = map(int, input().split())

H = coord_compress(H)
dp = SegmentTree([0] * len(H), max, 0)
for h, a in zip(H, A):
    dp.update(h, max(dp[h], dp.query(0, h) + a))
print(max(dp))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    

    
    
    


    
    
    
    
    
    

    
    N = int(input())
    
    
    

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        
        
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        
        
        
        
        update(H[i] - 1, dp[i])
        
        

    print (query(0, N, 0, 0, n))

if __name__ == '__main__':
    main()

Solution (Python):


def seg_tree_update(n,x):
    ind=2**m-1+n
    tree[ind]=x
    ind=(ind-1)//2
    while ind>=0:
        tree[ind]=max(tree[2*ind+1],tree[2*ind+2])
        ind=(ind-1)//2


def seg_tree_find_max(L,R):
    L,R=2**m-1+L,2**m-1+R
    qqq=0
    while L<R:
        if L%2==0:
            qqq=max(qqq,tree[L])
        if R%2==1:
            qqq=max(qqq,tree[R])
        L//=2
        R=R//2-1
        
    if L==R:
        qqq=max(qqq,tree[L])
    return qqq
  
N=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))

m=0
while pow(2,m)<N+1:
    m+=1
tree=[0]*(pow(2,m+1)-1)

for i in range(N):
    M=seg_tree_find_max(0,h[i])
    if tree[2**m-1+h[i]]<a[i]+M:
        seg_tree_update(h[i],a[i]+M)

ans=0
for i in range(N+1):
    ans=max(ans,tree[2**m-1+i])

print(ans)

Solution (Python):
def seg_tree_update(n,x):
    ind=2**m-1+n
    tree[ind]=x
    ind=(ind-1)//2
    while ind>=0:
        tree[ind]=max(tree[2*ind+1],tree[2*ind+2])
        ind=(ind-1)//2

def seg_tree_find_max(L,R):
    L,R=2**m-1+L,2**m-1+R
    qqq=0
    while L<R:
        if L%2==0:
            qqq=max(qqq,tree[L])
        if R%2==1:
            qqq=max(qqq,tree[R])
        L//=2
        R=R//2-1
        
    if L==R:
        qqq=max(qqq,tree[L])
    return qqq

N=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))

m=0
while pow(2,m)<N+1:
    m+=1
tree=[0]*(pow(2,m+1)-1)

for i in range(N):
    M=seg_tree_find_max(0,h[i])
    if tree[2**m-1+h[i]]<a[i]+M:
        seg_tree_update(h[i],a[i]+M)

ans=0
for i in range(N+1):
    ans=max(ans,tree[2**m-1+i])

print(ans)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class Segment_Tree:
    __slots__ = ['ide_ele', 'size', 'num', 'seg', 'segfunc']

    def __init__(self, size, func, element):
        
        self.ide_ele = element
        self.size = size

        
        self.num = 2 ** (self.size - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num

        
        self.segfunc = func

    def apply(self, apply_seq):
        
        for i in range(self.size):
            self.seg[i + self.num - 1] = apply_seq[i]    
        
        for i in range(self.num - 2, -1, -1) :
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
        
    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k-1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1],  self.seg[k * 2 + 2])
        
    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2 
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res


n = int(input())
H = list(map(int,input().split()))
A = list(map(int,input().split()))
st = Segment_Tree(n+1,max,0)
dp = [0] * (n+1)
for i in range(n):
  hi = H[i]; ai = A[i]
  st.update(hi,st.query(0,hi+1)+ai)
print(st.query(0,n+1))

Solution (Python):
import sys

class segTree():
    def __init__(self, N, value):
        d, k = 1, 0
        while d < N:
            d *= 2
            k += 1
        self.tree = [value for _ in range(2 * d - 1)]
        self.size = d
    
    def update(self, i, a):
        now = self.size - 1 + i 
        self.tree[now] = a
        while now > 0:
            now = (now - 1) // 2
            self.tree[now] = max(self.tree[2 * now + 1], self.tree[2 * now + 2])
        

    def search(self, lower, higher, lbound, hbound, pos):
        if higher <= lbound or hbound <= lower: return 0
        if lower <= lbound and hbound <= higher: return self.tree[pos]
        else:
            left = self.search(lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            right = self.search(lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            return max(left, right)
        
def solve():
    input = sys.stdin.readline
    N = int(input())
    H = [int(h) for h in input().split()]
    A = [int(a) for a in input().split()]
    highest = max(H) + 1
    ans = segTree(highest, 0)
    for i, h in enumerate(H): 
        maxSum = ans.search(0, h, 0, ans.size, 0)
        ans.update(h, A[i] + maxSum)
    print(ans.search(0, highest, 0, ans.size, 0))

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
class SegmentTree:
    def __init__(self, a, mode='min'):
        if mode == 'min':
            self.padding = float('inf')
            self.func = min
        elif mode == 'max':
            self.padding = -float('inf')
            self.func = max
        elif mode == 'sum':
            self.padding = 0
            self.func = sum
        
        n = len(a)
        self.N = 2 ** (n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = self.func([self.data[i], self.data[i-1]])
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = self.func([self.data[2*idx+1], self.data[2*idx+2]])
    
    def search(self, i, j):
        
        if i == j:
            return self.data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j 
            result = self.padding
            while idx1 + 1 < idx2:
                if idx1&1 == 0: 
                    result = self.func([result, self.data[idx1]])
                if idx2&1 == 1: 
                    result = self.func([result, self.data[idx2]])
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = self.func([result, self.data[idx1]])
            else: 
                result = self.func([result, self.data[idx1], self.data[idx2]])
            
            return result


N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))

dp = [0] * (N+1)
st = SegmentTree(dp, 'max')

ans = 0
for h, a in zip(H, A):
  M = st.search(0, h)
  st.update(h, M + a)

print(st.search(0, N+1))

Solution (Python):
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    
    
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)

    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="
                continue
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

def examI():
    N = I()
    P = LFI()
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(i+1):
            dp[i+1][j+1] += dp[i][j]*P[i]
            dp[i+1][j] += dp[i][j]*(1-P[i])
    ans = 0
    for v in dp[N][(1+N//2):]:
        ans += v
    print(ans)
    return

def examJ():
    N = I()
    A = LI()
    dp = [[[0]*(N+1) for _ in range(N+1)]for _ in range(N+1)]
    S = Counter(A)
    print(S)
    dp[S[1]][S[2]][S[3]] = 0
    que = deque()
    que.append((S[1],S[2],S[3]))
    used = defaultdict(set)
    while(que):
        n1,n2,n3 = que.popleft()
        if used[(n1,n2,n3)]:
            continue
        used[(n1,n2,n3)] = True
        now = n1+n2+n3
        if n1>0:
            dp[n1-1][n2][n3] += dp[n1][n2][n3] + N/now * n1/now
            que.append((n1-1, n2, n3))
        if n2>0:
            dp[n1+1][n2-1][n3] += dp[n1][n2][n3] + N/now * n2/now
            que.append((n1+1,n2-1,n3))
        if n3>0:
            dp[n1][n2+1][n3-1] += dp[n1][n2][n3] + N/now * n3/now
            que.append((n1,n2+1,n3-1))

    ans = dp[0][0][0]
    print(ans)
    return

def examK():
    N, K = LI()
    A = LI()
    dp = [-1]*(K+1)
    for i in range(1,K+1):
        flag = False
        for a in A:
            if a>i:
                break
            if dp[i-a]==-1:
                flag = True
                break
        if flag:
            dp[i] = 1

    ans = dp[K]
    if ans==1:
        print("First")
    else:
        print("Second")
    return

def examM():
    N, K = LI()
    A = LI()
    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        cum = [0]*(K+1)
        cum[0] = dp[i][0]
        for c in range(K):
            cum[c+1] = cum[c] + dp[i][c+1]
        for j in range(K+1):
            if j<=A[i]:
                dp[i+1][j] = cum[j]
            else:
                dp[i+1][j] = cum[j] - cum[j-A[i]-1]
            dp[i+1][j] %=mod

    ans = dp[N][K]%mod
    print(ans)
    return

def examN():
    N = I()
    A = LI()
    cumA = [0]*(N+1)
    for i in range(N):
        cumA[i+1] = cumA[i]+A[i]
    dp = [[inf]*(N) for _ in range(N)]
    for i in range(N):
        dp[0][i] = 0
    for i in range(N-1):
        for j in range(N-i-1):
            for k in range(i+1):
                cur = dp[i-k][j+k+1]+dp[k][j]+cumA[i+j+2]-cumA[j]
                dp[i+1][j] = min(dp[i+1][j],cur)

    ans = dp[N-1][0]
    print(ans)
    return

def examO():
    N = I()
    A = [LI() for _ in range(N)]
    loop = 2**N
    dp = [[0]*loop for _ in range(N+1)]
    dp[0][0] = 1
    for mask in range(loop):
        cur = 0
        for j in range(N):
            if mask&(1<<j)==(1<<j):
                cur +=1
        for i in range(N):
            if mask&(1<<i)==0 and A[i][cur]==1:
                dp[cur+1][mask|(1<<i)] += dp[cur][mask]
                dp[cur + 1][mask | (1 << i)] %=mod

    ans = dp[N][loop-1]
    print(ans)
    return

def examP():
    def dfs_dp(n,s,fords,visited):
        W = 1; B = 1
        visited[s] = True
        for v in fords[s]:
            if visited[v]:
                continue
            cur = dfs_dp(n, v, fords,visited)
            W *= sum(cur)
            B *= cur[0]
            W %= mod
            B %= mod

        return (W,B)
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        x,y = LI()
        x -=1; y -=1
        V[x].append(y)
        V[y].append(x)
    visited = [False]*N
    ans = dfs_dp(N,0,V,visited)
    print(sum(ans)%mod)
    return

def examQ():
    
    class segment_():
        def __init__(self, A, n, segfunc):
            
            self.ide_ele = 0
            
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            
            for i in range(n):
                self.seg[i + self.num] = A[i]
                
            for i in range(self.num - 1, 0, -1):
                self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

        def update(self, k, r):
            k += self.num
            self.seg[k] = r
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        
        def update1(self, k):
            k += self.num
            self.seg[k] += 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def updateneg1(self, k):
            k += self.num
            self.seg[k] -= 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def query(self, p, q):
            if q < p:
                return self.ide_ele
            p += self.num;
            q += self.num
            res = self.ide_ele
            while p < q:
                if p & 1 == 1:
                    res = self.segfunc(res, self.seg[p])
                    p += 1
                if q & 1 == 1:
                    q -= 1
                    res = self.segfunc(res, self.seg[q])
                p >>= 1;
                q >>= 1
            return res
    N = I()
    H = LI()
    maxH = max(H)
    A = LI()
    Seg_max = segment_([0]*(maxH+1), (N+1), lambda a, b: max(a,b))
    dp = [0]*(maxH+1)
    cur = 0
    for i in range(N):
        h = H[i]
        cur = Seg_max.query(0,h+1)
        dp[i] = cur + A[i]
        Seg_max.update(h,dp[i])
    ans = max(dp)
    print(ans)
    return

def examR():
    def list_dot(A1,A2):
        res = [[0]*len(A2) for _ in range(len(A1))]
        for i in range(len(A1)):
            for j in range(len(A2)):
                cur = 0
                for k in range(len(A1[0])):
                    cur += A1[i][k]*A2[k][j]
                res[i][j] = cur%mod
        return res
    N, K = LI()
    A = [LI() for _ in range(N)]
    now = [[1]*N]
    while(K>0):
        if K%2==1:
            now = list_dot(now,A)
        K //=2
        A = list_dot(A,A)
    ans = 0
    for i in now:
        for k in i:
            ans += k
            ans %= mod
    print(ans)
    return

def examS():
    class ModInt:
        def __init__(self, x):
            self.x = x % MOD

        def __str__(self):
            return str(self.x)

        __repr__ = __str__

        def __add__(self, other):
            return (
                ModInt(self.x + other.x) if isinstance(other, ModInt) else
                ModInt(self.x + other)
            )

        def __sub__(self, other):
            return (
                ModInt(self.x - other.x) if isinstance(other, ModInt) else
                ModInt(self.x - other)
            )

        def __mul__(self, other):
            return (
                ModInt(self.x * other.x) if isinstance(other, ModInt) else
                ModInt(self.x * other)
            )

        def __truediv__(self, other):
            return (
                ModInt(
                    self.x * pow(other.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(self.x * pow(other, MOD - 2, MOD))
            )

        def __pow__(self, other):
            return (
                ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(self.x, other, MOD))
            )

        __radd__ = __add__

        def __rsub__(self, other):
            return (
                ModInt(other.x - self.x) if isinstance(other, ModInt) else
                ModInt(other - self.x)
            )

        __rmul__ = __mul__

        def __rtruediv__(self, other):
            return (
                ModInt(
                    other.x * pow(self.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(other * pow(self.x, MOD - 2, MOD))
            )
        def __rpow__(self, other):
            return (
                ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(other, self.x, MOD))
            )
    def ketadp(a,D):
        n = len(a)
        dp = [[[ModInt(0)]*D for _ in range(2)] for _ in range(n+1)]
        dp[0][0][0] = 1
        for i, less, hasD in itertools.product(range(n), (0, 1), range(D)):
            max_d = 9 if less else int(a[i])
            for d in range(max_d + 1):
                less_ = less or d < max_d
                hasD_ = (hasD + d)%D
                dp[i + 1][less_][hasD_] += dp[i][less][hasD]

        ans = sum(dp[n][less][0] for less in (0, 1))
        return ans
    K = SI()
    D = I()
    ans = ketadp(K,D)
    ans = ans-1
    print(ans)
    return

def examT():
    return

def examU():
    N = I()
    A = [LI() for _ in range(N)]
    mask = 2**N
    cst = [0]*mask
    for i in range(mask):
        cur = 0
        for j in range(N):
            for k in range(j+1,N):
                if i&(1<<j)==(1<<j) and i&(1<<k)==(1<<k):
                    cur += A[j][k]
        cst[i] = cur
    dp = [0]*mask
    for m in range(mask):
        maskT = m
        while(maskT > 0):
            cur = dp[m-maskT] + cst[maskT]
            dp[m] = max(dp[m], cur)

            
            maskT = (maskT - 1) & m

    ans = dp[-1]
    print(ans)
    return

def examX():
    N = I()
    W = [[] for _ in range(N)]
    for i in range(N):
        W[i] = LI()
    W.sort(key=lambda x:x[1])
    maxS = W[-1][1]
    print(W)
    dp = [[0]*(maxS+2) for _ in range(N+1)]
    for i in range(N):
        ns = W[i][1]
        nw = W[i][0]
        nv = W[i][2]
        for j in range(maxS+2):
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        for j in range(ns+1):
            dp[i+1][min(j+nw,maxS+1)] = max(dp[i+1][j],dp[i][j]+nv)
    ans = max(dp[N])
    print(dp)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,MOD
mod = 10**9 + 7
mod2 = 998244353
MOD = mod
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examQ()

"""

"""

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class RangeMinimumQuery:
    def __init__(self, n, func=min, inf=float("inf")):
        self.n0 = 2**(n-1).bit_length()
        self.op = func
        self.inf = inf
        self.data = [self.inf]*(2*self.n0)

    
    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.inf
        while l < r:
            if r&1:
                r -= 1
                res = self.op(res, self.data[r-1])
            if l&1:
                res = self.op(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i:
            i = ~-i//2
            self.data[i] = self.op(self.data[2*i+1], self.data[2*i+2])

n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

RMQ = RangeMinimumQuery(n, func=max, inf=0)

for i in range(n):
    hi, ai = h[i], a[i]
    s = RMQ.query(0, hi-1)
    RMQ.update(hi-1, s+ai)

ans = RMQ.query(0, n)
print(ans)

Solution (Python):
def main():
    input()
    H=map(int,input().split())
    A=map(int,input().split())
    n=2*10**5+1

    def update_max(k,x):
        k += num_max-1
        seg_max[k] = x
        while k:
            k = (k-1)//2
            seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    def query_max(p,q):
        if q<=p:
            return ide_ele_max
        p += num_max-1
        q += num_max-2
        res=ide_ele_max
        while q-p>1:
            if p&1 == 0:
                res = max(res,seg_max[p])
            if q&1 == 1:
                res = max(res,seg_max[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = max(res,seg_max[p])
        else:
            res = max(max(res,seg_max[p]),seg_max[q])
        return res
    ide_ele_max = 0
    num_max =2**(n-1).bit_length()
    seg_max=[ide_ele_max]*2*num_max

    for h,a in zip(H,A):
        update_max(h,query_max(0,h)+a)
    
    print(query_max(0,n))
main()

Solution (Python):
class SegmentTreeMax:
    def __init__(self, a):
        self.padding =  -float('inf')
        
        n = len(a)
        self.N = 2 ** (n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = max(self.data[i], self.data[i-1])
    
    def update(self, idx, x):
        idx = self.N - 1 + idx
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = max(self.data[2*idx+1], self.data[2*idx+2])
    
    def search(self, i, j):
        if i == j:
            return self.data[self.N - 1 + i]
        else:
            idx1 = self.N-1+i
            idx2 = self.N-1+j-1
            result = self.padding
            while idx1 + 1 < idx2:
                if idx1&1 == 0: 
                    result = max(result, self.data[idx1])
                if idx2&1 == 1: 
                    result = max(result, self.data[idx2])
                    idx2 -= 1

                idx1 //= 2
                idx2 = (idx2 - 1)//2

            if idx1 == idx2:
                result = max(result, self.data[idx1])
            else: 
                result = max(result, self.data[idx1], self.data[idx2])

            return result


N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))

dp = [0] * N
st = SegmentTreeMax(dp)

ans = 0
for h, a in zip(H, A):
  M = st.search(0, h-1)
  st.update(h-1, M + a)
  
print(st.search(0, N))

Solution (Python):
class SegmentTreeMax:
    def __init__(self, a):
        self.padding =  -float('inf')
        
        n = len(a)
        self.N = 2 ** (n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = max(self.data[i], self.data[i-1])
    
    def update(self, idx, x):
        idx = self.N - 1 + idx
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = max(self.data[2*idx+1], self.data[2*idx+2])
    
    def search(self, i, j):
        
        idx1 = self.N-1+i
        idx2 = self.N-1+j-1
        result = self.padding
        while idx1 + 1 < idx2:
            if idx1&1 == 0: 
                result = max(result, self.data[idx1])
            if idx2&1 == 1: 
                result = max(result, self.data[idx2])
                idx2 -= 1
            
            idx1 //= 2
            idx2 = (idx2 - 1)//2
        
        if idx1 == idx2:
            result = max(result, self.data[idx1])
        else: 
            result = max(result, self.data[idx1], self.data[idx2])
        
        return result


N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))

dp = [0] * (N+1)
st = SegmentTreeMax(dp)

ans = 0
for h, a in zip(H, A):
  M = st.search(0, h)
  st.update(h, M + a)

print(st.search(0, N+1))