Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def main():
    H, W = map(int, input().split())
    matrix = [list(input()) for _ in range(H)]
    L = [[0 for _ in range(W)] for _ in range(H)]
    R = [[0 for _ in range(W)] for _ in range(H)]
    D = [[0 for _ in range(W)] for _ in range(H)]
    U = [[0 for _ in range(W)] for _ in range(H)]
    S = [[0 for _ in range(W)] for _ in range(H)]

    # 左方向についてカウントする
    for i in range(H):
        if matrix[i][0] == '.':
            L[i][0] = 1
            S[i][0] += 1
        for j in range(1, W):
            s = matrix[i][j]
            if s == '.':
                L[i][j] = L[i][j-1] + 1
                S[i][j] += L[i][j]

    # 右方向についてカウントする
    for i in range(H):
        if matrix[i][-1] == '.':
            R[i][-1] = 1
            S[i][-1] += 1
        for j in range(W-2, -1, -1):
            s = matrix[i][j]
            if s == '.':
                R[i][j] = R[i][j+1] + 1
                S[i][j] += R[i][j]
    
    # 上方向についてカウントする
    for i in range(W):
        if matrix[0][i] == '.':
            U[0][i] = 1
            S[0][i] += 1
        for j in range(1, H):
            s = matrix[j][i]
            if s == '.':
                U[j][i] = U[j-1][i] + 1
                S[j][i] += U[j][i]
    
    # 下方向についてカウントする
    for i in range(W):
        if matrix[-1][i] == '.':
            D[-1][i] = 1
            S[-1][i] += 1
        for j in range(H-2, -1, -1):
            s = matrix[j][i]
            if s == '.':
                D[j][i] = D[j+1][i] + 1
                S[j][i] += D[j][i]
    
    
    max_val = -3
    for i in range(H):
        for j in range(W):
            max_val = max(max_val, S[i][j])
    print(max_val-3)
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    matrix = [list(input()) for _ in range(H)]
    L = [[0 for _ in range(W)] for _ in range(H)]
    R = [[0 for _ in range(W)] for _ in range(H)]
    D = [[0 for _ in range(W)] for _ in range(H)]
    U = [[0 for _ in range(W)] for _ in range(H)]

    # 左方向についてカウントする
    for i in range(H):
        if matrix[i][0] == '.':
            L[i][0] = 1
        for j in range(1, W):
            s = matrix[i][j]
            if s == '.':
                L[i][j] = L[i][j-1] + 1

    # 右方向についてカウントする
    for i in range(H):
        if matrix[i][-1] == '.':
            R[i][-1] = 1
        for j in range(W-2, -1, -1):
            s = matrix[i][j]
            if s == '.':
                R[i][j] = R[i][j+1] + 1
    
    # 上方向についてカウントする
    for i in range(W):
        if matrix[0][i] == '.':
            U[0][i] = 1
        for j in range(1, H):
            s = matrix[j][i]
            if s == '.':
                U[j][i] = U[j-1][i] + 1
    
    # 下方向についてカウントする
    for i in range(W):
        if matrix[-1][i] == '.':
            D[-1][i] = 1
        for j in range(H-2, -1, -1):
            s = matrix[j][i]
            if s == '.':
                D[j][i] = D[j+1][i] + 1    
    
    max_val = -3
    for i in range(H):
        for j in range(W):
            max_val = max(max_val, R[i][j]+L[i][j]+U[i][j]+D[i][j])
    print(max_val-3)
    return

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, Q = map(int, input().split())

S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

from collections import defaultdict
stops = defaultdict(lambda: -1)
for x, s, t in roadworks:
    for i in range(s, t+1):
        i = max(0, i-x)
        stops[i] = x
#print(stops)
for d in D:
    print(stops[d+1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())

S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, key=lambda x: x[0])
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * Q
skip = [-1] * Q

import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    
    i = left
    while i < right:
        if skip[i] == -1:
            ans[i] = x
            skip[i] = right
            i += 1
        else:
            i = skip[i]

    
#print(walkers)
for a in ans:
    print(a)
### BUGGY CODE ###

k=int(input())
num=0

while k>0:
  num+=1
  snum=str(num)
  flg=0
  for i in range(0,len(snum)-1):
    if abs(int(snum[-1-i])-int(snum[-2-i]))>1:  
      flg=1
      break
  if flg==0:
    k-=1
print(num)

### FIXED CODE ###

k=int(input())
num=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]
keta=0
for i in range(0,k):
  for j in range(0,len(num)-1):
    if num[j]==-1:
      num[j]=1
      keta=j
      break
    elif num[j]!=9 and (num[j+1]==-1 or (num[j]-num[j+1])<1):
      num[j]+=1
      break
  for x in range(j-1,-1,-1):
    num[x]=max(0,num[x+1]-1)

for i in range(keta,-1,-1):
  print(num[i],end='')
print()
### BUGGY CODE ###

h,w = map(int,input().split())
a1 = [[1000] * (w+2) for i in range(h+2)]
a2 = [['.'] * (w+2) for i in range(h+2)]
for i in range(h):
  a2[i+1][1:-1] = list(input())
for i in range(h):
  for j in range(w):
    if a2[i+1][j+1] == '#':
      a1[i+1][j+1] = 0
for i in range(w):
  for j in range(h):
    a1[j+1][i+1] = min(a1[j][i+1]+1,a1[j+1][i+1])
for i in range(w):
  for j in range(h):
    a1[h-j][i+1] = min(a1[h-j+1][i+1]+1,a1[h-j][i+1])
for i in range(h):
  for j in range(w):
    a1[i+1][j+1] = min(a1[i+1][j]+1,a1[i+1][j+1])
for i in range(h):
  for j in range(w):
    a1[i+1][w-j] = min(a1[i+1][w-j+1]+1,a1[i+1][w-j])
m = 0
for i in range(h):
  for j in range(w):
    m = max(m,a1[i+1][j+1])
print(m)

### FIXED CODE ###

h,w = map(int,input().split())
a1 = [[5000] * (w+2) for i in range(h+2)]
a2 = [['.'] * (w+2) for i in range(h+2)]
for i in range(h):
  a2[i+1][1:-1] = list(input())
for i in range(h):
  for j in range(w):
    if a2[i+1][j+1] == '#':
      a1[i+1][j+1] = 0
for i in range(w):
  for j in range(h):
    a1[j+1][i+1] = min(a1[j][i+1]+1,a1[j+1][i+1])
for i in range(w):
  for j in range(h):
    a1[h-j][i+1] = min(a1[h-j+1][i+1]+1,a1[h-j][i+1])
for i in range(h):
  for j in range(w):
    a1[i+1][j+1] = min(a1[i+1][j]+1,a1[i+1][j+1])
for i in range(h):
  for j in range(w):
    a1[i+1][w-j] = min(a1[i+1][w-j+1]+1,a1[i+1][w-j])
m = 0
for i in range(h):
  for j in range(w):
    m = max(m,a1[i+1][j+1])
print(m)
### BUGGY CODE ###

def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        k = int(k)
        ndp = [0] * d

        for di, dk in enumerate(dp):
            for ndi in range(di, di + 10):
                ndp[ndi % d] += dk

        for ndi in range(just, just + k):
            ndp[ndi % d] += 1

        for ndk in ndp:
            ndk %= md

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = input()
d = int(input())
f(ks, d)


### FIXED CODE ###

def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        ndp = [0] * d

        for di, dk in enumerate(dp):
            for ndi in range(di, di + 10):
                ndp[ndi % d] += dk

        for ndi in range(just, just + k):
            ndp[ndi % d] += 1

        ndp = [ndk % md for ndk in ndp]

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = list(map(int, list(input())))
d = int(input())
f(ks, d)
### BUGGY CODE ###

L,R = map(int, input().split())
rec = 2019
for i in range (R - L +1):
    for j in range(R - L +1):
        if i >= j:
            continue
        elif (((L+i)*(L+j)) % 2019) < rec:
            rec = ((L+i)*(L+j)) % 2019
print(rec)


### FIXED CODE ###

L,R = map(int, input().split())
rec = 2019
for i in range (2020):
    for j in range(2020):
        if i >= j or (L+j) > R:
            continue
        elif (((L+i)*(L+j)) % 2019) < rec:
            rec = ((L+i)*(L+j)) % 2019
print(rec)
### BUGGY CODE ###

n,k = (int(_) for _ in input().split())

c = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        if (i+j)%k != 0:
            continue
        for a in range(1,n+1):
            if (j+a)%k == 0 and (a+i)%k == 0:
                c += 1
            else:
                continue

print(c)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math

def solve(N: int, K: int):

    ans = int(N/K) ** 3

    if(K%2 == 0):
        cnt = 0
        for i in range(int(K/2), N+1, K):
            cnt += 1
        ans += cnt ** 3
    
    print(ans)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = input()
Q = int(input())
d = 0 # d=0:right, d=1:left
for i in range(Q):
  I = list(input().split())
  if I[0] == "1":
    d ^= 1
  else:
    if d + int(I[1]) == 2:
      S = S + I[2]
    else:
      S = I[2] + S
if d == 1:
  S = S[::-1]
print(S)

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
d = 0 # d=0:right, d=1:left
for i in range(Q):
  I = list(input().split())
  if I[0] == "1":
    d ^= 1
  else:
    if d + int(I[1]) == 2:
      S.append(I[2])
    else:
      S.appendleft(I[2])
if d == 1:
  S.reverse()
for s in S:
  print(s, end="")
print()
### BUGGY CODE ###

N = int(input())
S = str(input())
we = list(S)
i = 0
min = N
while i < N:
  west = we[0:i]
  east = we[i+1:N]
  wcount = west.count("W")
  ecount = east.count("E")
  if min >= wcount+ecount:
    min = wcount+ecount
  i+=1
print(min)

### FIXED CODE ###

#C
N = int(input())
S = list(str(input()))
look_east = [0]
E = 0
W = 0
for s in S:
    if s == "E":
        look_east.append(look_east[-1]+1)
        E+=1
    else:
        look_east.append(look_east[-1])
        W+=1

ans = N
for i in range(N):
    we = look_east[i]
    if S[i] == "E":
        change = i-we + E-(we+1)
    else:
        change = i-we + E-(we)
        
    ans = min(ans,change)
        
print(ans)
### BUGGY CODE ###

import sys
import copy
input = sys.stdin.readline

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

SUM=0
for a in A:
    SUM+=a
    if SUM>=K:
        MAX_NO_NEED=a
        break

else:
    print(N)
    sys.exit()
        

#A=[a for a in A if a<K]
L=len(A)

MIN=-1
MAX=A.index(MAX_NO_NEED)-1

while MIN!=MAX:

    x=(MIN+MAX+1)//2
    base=A[x]

    SET={base}
    flag=0
    
    for i in range(L):
        #print(x,i,SET)
        if i==x:
            continue
        a=A[i]
        NSET=copy.copy(SET)
        
        for j in SET:
            
            if K<=a+j<K+base:
                flag=1
                break
            elif a+j<K:
                NSET.add(a+j)

        if flag==1:
            #print(x,SET)
            MAX=x-1
            break

        SET=NSET

    else:
        MIN=x
        continue

print(MIN+1)

    


### FIXED CODE ###

import sys
import copy
input = sys.stdin.readline

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

SUM=0
for a in A:
    SUM+=a
    if SUM>=K:
        MAX_NO_NEED=a
        break

else:
    print(N)
    sys.exit()
        

MAX=A.index(MAX_NO_NEED)-1

A=[a for a in A if a<K]
L=len(A)

MIN=-1
MAX=min(MAX,L-1)

while MIN!=MAX:

    x=(MIN+MAX+1)//2
    base=A[x]

    SET={base}
    flag=0
    
    for i in range(L):
        #print(x,i,SET)
        if i==x:
            continue
        a=A[i]
        NSET=copy.copy(SET)
        
        for j in SET:
            
            if K<=a+j<K+base:
                flag=1
                break
            elif a+j<K:
                NSET.add(a+j)

        if flag==1:
            #print(x,SET)
            MAX=x-1
            break

        SET=NSET

    else:
        MIN=x
        continue

print(MIN+1)
### BUGGY CODE ###

N, K = map(int, input().split())

area = []
for i in range(K):
    L, R = map(int, input().split())
    area.append((L, R))

area.sort()
d = [0] * N
a = [0] * N


def func(pos):
    for l, r in area:
        if pos + l - 1 < N:
            a[pos + l-1] += d[pos]
        if pos + r < N:
            a[pos + r] -= d[pos]
    d[pos+1] = d[pos] + a[pos]


d[0] = 1
a[0] = -1
for i in range(0, N-1):
    func(i)

print(d[N-1] % 998244353)


### FIXED CODE ###

N, K = map(int, input().split())

area = []
for i in range(K):
    L, R = map(int, input().split())
    area.append((L, R))

area.sort()
d = [0] * N
a = [0] * N


def func(pos):
    for l, r in area:
        if pos + l - 1 < N:
            a[pos + l-1] += d[pos]
        if pos + r < N:
            a[pos + r] -= d[pos]
    d[pos+1] = (d[pos] + a[pos]) % 998244353


d[0] = 1
a[0] = -1
for i in range(0, N-1):
    func(i)

print(d[N-1] % 998244353)
### BUGGY CODE ###

import numpy as np

M = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

zero = np.zeros(62, dtype=np.int64)
one = np.ones(62, dtype=np.int64)
pow2 = (2 ** np.arange(62, dtype=np.int64)) % M


def bitcnt(a):
    j = 0
    bits = np.zeros(62, dtype=np.int64)
    while a:
        bits[j] = a & 1
        a >>= 1
        j += 1
    return bits


ans = 0
a1 = bitcnt(A[0])
a0 = one - a1
for i in range(1, N):
    bits1 = bitcnt(A[i])
    bits0 = one - bits1
    ans += np.sum(pow2 * (a0 * bits1 % M) % M) % M
    ans %= M
    ans += np.sum(pow2 * (a1 * bits0 % M) % M) % M
    ans %= M
    a1 += bits1
    a1 %= M
    a0 += bits0
    a0 %= M

print(ans)


### FIXED CODE ###

M = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

zero = [0] * 60
one = [1] * 60
pow2 = [2 ** i % M for i in range(60)]


def bitcnt(a):
    j = 0
    bits = [0] * 60
    while a:
        bits[j] = a & 1
        a >>= 1
        j += 1
    return bits


ans = 0
a1 = bitcnt(A[0])
a0 = [(x + 1) % 2 for x in a1]
for i in range(1, N):
    a = A[i]
    for j in range(60):
        b1 = a & 1
        a >>= 1
        if b1:
            ans += pow2[j] * a0[j] % M
            a1[j] += 1
        else:
            ans += pow2[j] * a1[j] % M
            a0[j] += 1
        ans %= M

print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

t = int(input())

nabcd = [tuple(map(int,input().split())) for i in range(t)]

INF = float('inf')
from functools import lru_cache
@lru_cache(None)
def dfs(now,cost,a,b,c,d):
    if now == 0:
        return cost
    elif now == 1:
        return cost + d
    elif now == 2:
        return min(cost+d+a, cost+d*2)
    elif now <0:
        return INF

    tmp = cost + now*d

    # over 2
    sho = now//2+1
    fusoku = sho*2 - now
    over2 = dfs(sho,cost+d*fusoku+a,a,b,c,d)

    # not over 2
    sho = now//2
    amari = now-sho*2
    nver2 = dfs(sho,cost+d*amari+a,a,b,c,d)

    # over 3
    sho = now//3+1
    fusoku = sho*3 - now
    over3 = dfs(sho,cost+d*fusoku+b,a,b,c,d)

    # not over 3
    sho = now//3
    amari = now-sho*3
    nver3 = dfs(sho,cost+d*amari+b,a,b,c,d)

    # over 5
    sho = now//5+1
    fusoku = sho*5 - now
    over5 = dfs(sho,cost+d*fusoku+c,a,b,c,d)

    # not over 5
    sho = now//5
    amari = now-sho*5
    nver5 = dfs(sho,cost+d*amari+c,a,b,c,d)

    return min(tmp,over2,nver2,over3,nver3,over5,nver5)


for n,a,b,c,d in nabcd:
    ans = dfs(n,0,a,b,c,d)
    print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

t = int(input())

nabcd = [tuple(map(int,input().split())) for i in range(t)]

INF = float('inf')
from functools import lru_cache

for n,a,b,c,d in nabcd:

    @lru_cache(None)
    def dfs(now):
        if now == 0:
            return 0
        elif now == 1:
            return d
        elif now == 2:
            return min(d+a, d*2)
        elif now <0:
            return INF

        tmp = now*d

        # over 2
        sho = now//2+1
        fusoku = sho*2 - now
        over2 = dfs(sho)+d*fusoku+a

        # not over 2
        sho = now//2
        amari = now-sho*2
        nver2 = dfs(sho)+d*amari+a

        # over 3
        sho = now//3+1
        fusoku = sho*3 - now
        over3 = dfs(sho)+d*fusoku+b

        # not over 3
        sho = now//3
        amari = now-sho*3
        nver3 = dfs(sho)+d*amari+b

        # over 5
        sho = now//5+1
        fusoku = sho*5 - now
        over5 = dfs(sho)+d*fusoku+c

        # not over 5
        sho = now//5
        amari = now-sho*5
        nver5 = dfs(sho)+d*amari+c

        return min(tmp,over2,nver2,over3,nver3,over5,nver5)

    ans = dfs(n)
    print(ans)
### BUGGY CODE ###

m = 10000
g = 5000
s = 1000
n, y = map(int, input().split())
if y > n * m or y < n * s:
    print("-1 -1 -1")
    exit()
if y / n == 10000:
    print(n, "0 0")
    exit()
elif y / n == 5000:
    print("0", n, "0")
    exit()
elif y / n == 1000:
    print("0 0", n)
    exit()
if y / n > 7500:
    for i in range(n):
        for j in range(n - i+1):
            for h in range(n - j+1):
                if i * s + j * g + h * m == y and i + j + h == n:
                    print(h, j, i)
                    exit()
    else:
        print("-1 -1 -1")
elif y/n > 3000:
    for i in range(n):
        for j in range(n - i+1):
            for h in range(n - j+1 - i):
                if i * s + j * m + h * g == y and i + j + h == n:
                    print(j, h, i)
                    exit()
    else:
        print("-1 -1 -1")
else:
    for i in range(n):
        for j in range(n-i+1):
            for h in range(n-j+1 - i):
                if i*m+j*g+h*s==y and i+j+h == n:
                    print(i, j, h)
                    exit()
    else:
        print("-1 -1 -1")

### FIXED CODE ###

n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n - i + 1):
        if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
            print(i, j, n - i - j)
            exit()
print("-1 -1 -1")
### BUGGY CODE ###

N,K = map(int,input().split())
S = input()

arr = []
now = S[0]
if now == "1":
    count = 1
else:
    count = -1
for c in S[1:]:
    next = c
    if c == now:
        if now == "1":
            count += 1
        else:
            count -= 1
    else:
        arr.append(count)
        if now == "1":
            count = -1
            now = "0"
        else:
            count = 1
            now = "1"
arr.append(count)

anss = []
Sum = 0
if arr[0] >= 0:
    head = 0
else:
    head = 0
    arr = [0] + arr
while head+2*K <= len(arr):
    tail = head+2*K
    Sum += sum(map(abs, arr[head:tail+1]))
    anss.append(Sum)
    head += 2
    Sum = 0
if anss == []:
    ans = sum(map(abs,arr))
else:
    ans = max(anss)
print(ans)

### FIXED CODE ###

from itertools import accumulate
N,K = map(int,input().split())
S = input()

arr = []
now = S[0]
if now == "1":
    count = 1
else:
    count = -1
for c in S[1:]:
    next = c
    if c == now:
        if now == "1":
            count += 1
        else:
            count -= 1
    else:
        arr.append(count)
        if now == "1":
            count = -1
            now = "0"
        else:
            count = 1
            now = "1"
arr.append(count)

anss = []
Sum = 0
head = 0
if arr[0] < 0:
    arr = [0] + arr
arr2 = [0] + list(accumulate(list(map(abs, arr))))
while head+2*K <= len(arr):
    tail = head+2*K
    Sum += arr2[tail+(tail < len(arr2)-1)]-arr2[head]
    #Sum += sum(map(abs, arr[head:tail+1]))
    anss.append(Sum)
    head += 2
    Sum = 0
if anss == []:
    ans = sum(map(abs,arr))
else:
    ans = max(anss)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input())
B=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[0]+x[1])
#W+Sの順にソートすると無駄がない。

DP=[0]*(10**4+2)
#重さの合計がWのときの価値。
#W=10**4+1ならそれ以上更新されないので、W>=10**4+1以上のものはそこに置く

for w,s,v in B:
    
    if 10**4+1-w<=s:
        if DP[-1]<max(DP[10**4+1-w:s+1])+v:
            DP[-1]=max(DP[10**4+1-w:s+1])+v
        
    for i in range(min(10**4-w,s),-1,-1):
        if DP[i+w]<DP[i]+v:
            DP[i+w]=DP[i]+v

print(max(DP))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
B=[list(map(int,input().split())) for i in range(N)]

B.sort(key=lambda x:x[0]+x[1])
#W+Sの順にソートすると無駄がない。

DP=[0]*(10**4+2)
#重さの合計がWのときの価値。
#W=10**4+1ならそれ以上更新されないので、W>=10**4+1以上のものはそこに置く

for w,s,v in B:
    for i in range(s,-1,-1):
        if i+w<=10**4:
            if DP[i+w]<DP[i]+v:
                DP[i+w]=DP[i]+v

        else:
            if DP[-1]<DP[i]+v:
                DP[-1]=DP[i]+v

print(max(DP))
### BUGGY CODE ###

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
ans = 'NO'
for i in range(t):
    if a < b:
        a += v
        b += w
    else:
        a -= v
        b -= w
    if a == b:
        ans = 'YES'
        break
print(ans)


### FIXED CODE ###

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
if abs(a - b) <= (v -w) * t:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

from math import ceil

h, w = map(int, input().split())
s = [input() for _ in range(h)]

n = h * w

dp = [[[float("inf")] * 2 for _ in range(n + 1)] for _ in range(n + 1)]
if s[0][0] == "#":
    dp[1][1][1] = 1
else:
    dp[1][1][0] = 0

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i-1][j-1] == "#":
            dp[i][j][1] = min(dp[i][j][1], dp[i-1][j][0] + 1, dp[i-1][j][1], dp[i][j-1][0] + 1, dp[i][j-1][1])
        else:
            dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][0], dp[i-1][j][1] + 1, dp[i][j-1][0], dp[i][j-1][1] + 1)

idx = 1 if s[h-1][w-1] == "#" else 0
ans = dp[h][w][idx]
ans = ceil(ans / 2)
print(ans)


### FIXED CODE ###

from math import ceil
from collections import defaultdict

h, w = map(int, input().split())
s = [input() for _ in range(h)]

n = h * w
INF = 100 * 100

dp = defaultdict(lambda: INF)
if s[0][0] == "#":
    dp[(1, 1, 1)] = 1
else:
    dp[(1, 1, 0)] = 0

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i-1][j-1] == "#":
            dp[(i, j, 1)] = min(dp[(i, j, 1)], dp[(i-1, j, 0)] + 1, dp[(i-1, j, 1)], dp[(i, j-1, 0)] + 1, dp[(i, j-1, 1)])
        else:
            dp[(i, j, 0)] = min(dp[(i, j, 0)], dp[(i-1, j, 0)], dp[(i-1, j, 1)] + 1, dp[(i, j-1, 0)], dp[(i, j-1, 1)] + 1)

idx = 1 if s[h-1][w-1] == "#" else 0
ans = dp[(h, w, idx)]
ans = ceil(ans / 2)
print(ans)
### BUGGY CODE ###

k=int(input())
a=7
count=1
if k%2==0:
  print(-1)
else:
  while True:
    if a%k==0:
      print(count)
      break
    else:
      a=a*10+7
      count+=1


### FIXED CODE ###

k=int(input())
a=0
for i in range(k):
  a=(a*10+7)%k
  if a==0:
    print(i+1)
    exit()
    
print(-1)
### BUGGY CODE ###

import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    nex_num = a[-1] // 2
    del a[-1]
    a.insert(bisect.bisect_left(a, nex_num), nex_num)
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a_minus = [-x for x in a]
import heapq
heapq.heapify(a_minus)
for i in range(m):
    nex_num = heapq.heappop(a_minus)
    nex_num = (-1 * nex_num) // 2 * -1
    heapq.heappush(a_minus, nex_num)
print(-sum(a_minus))