状态机dp（Python）

思路：非常裸的状态机dp板子题，挺典型的，建议没有接触过状态机dp的朋友们好好学习

代码：

import sys
input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

def solve():
    n, k = MII()
    a = LII()
    b = LII()
    dp = [[-inf] * 2 for _ in range(n + 1)]
    dp[1][0] = a[0]
    for i in range(1, n):
        dp[i + 1][0] = fmax(dp[i][0], dp[i][1] - k) + a[i] \
                            if dp[i][1] >= k else dp[i][0] + a[i]
        dp[i + 1][1] = fmax(dp[i][1], dp[i][0] - k) + b[i] \
                            if dp[i][0] >= k else dp[i][1] + b[i]
    print(fmax(dp[n][0], dp[n][1]))

t = 1
# t = II()
for _ in range(t):
    solve()