Coding 공부

N, M  = map(int,input().split())
not_visited_days = [True]*(N+1)
if M:
    for k in list(map(int,input().split())):
        not_visited_days[k] = False
        

INF = float('inf')
dp = [[INF for _ in range(40)] for _ in range(105)] 

dp[0][0] = 0


for day in range(N):
    for coupon in range(37):
        if not not_visited_days[day+1]:
            dp[day+1][coupon] = min(dp[day+1][coupon],dp[day][coupon])
        dp[day+1][coupon] = min(dp[day+1][coupon],dp[day][coupon] + 10000)
        dp[day+3][coupon+1] = min(dp[day+3][coupon+1],dp[day][coupon] + 25000)
        dp[day+5][coupon+2] = min(dp[day+5][coupon+2],dp[day][coupon] + 37000)

    for coupon in range(39,2,-1):
        dp[day+1][coupon-3] = min(dp[day+1][coupon-3],dp[day][coupon])
    

print(min(dp[N]))
    
    
    

N,K = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
diff = [0]*N
for i in range(N-1):
    diff[i] = arr[i+1] - arr[i]

diff.sort()
print(sum(diff[:len(diff)-(K-1)]))

import heapq
import sys

def dijkstra(S,E,TERM):
    INF = float('inf')
    distance_list = [INF]*(N+1)
    distance_list[S] = TERM
    node_list = []
    heapq.heappush(node_list,(TERM,S))

    while node_list:
        cur_time,cur_node = heapq.heappop(node_list)

        for next_node in graph[cur_node]:
            if time_spend_list.get((cur_node,next_node)) and time_spend_list[(cur_node,next_node)][0]<=cur_time<=time_spend_list[(cur_node,next_node)][1]:
                spend_time = time_spend_list[(cur_node,next_node)][1] + graph[cur_node][next_node]
            else:
                spend_time = cur_time + graph[cur_node][next_node]
            
            if distance_list[next_node] > spend_time:
                distance_list[next_node] = spend_time
                heapq.heappush(node_list,(spend_time,next_node))

    return distance_list


input = sys.stdin.readline

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

start_point,end_point,king_term,G = map(int,input().split())

king_visit_list = list(map(int,input().split()))


graph = [{} for _ in range(N+1)]

for _ in range(M):
    x,y,times = map(int,input().split())

    graph[x][y] = min(graph[x].get(y,float('inf')),times)
    graph[y][x] = min(graph[y].get(x,float('inf')),times)



time_spend_list = {}

king_time = 0
for ind in range(G-1):
    start,ends = king_visit_list[ind],king_visit_list[ind+1]
    time_spend_list[(start,ends)] = (king_time,king_time+graph[start][ends])
    time_spend_list[(ends,start)] = (king_time,king_time+graph[start][ends])
    king_time += graph[start][ends]


result = dijkstra(start_point,end_point,king_term)


print(result[end_point]-king_term)

import sys

sys.setrecursionlimit(100001)


def dfs(node):
    visited[node] = True
    child_node = []
    for next_node in graph[node]:
        if not visited[next_node]:
            child_node.append(next_node)
    if not len(child_node):
        dp[node][0] = 1
        return
    else:
        for child in child_node:
            dfs(child)

        for child in child_node:
            if dp[child][0]:
                dp[node][1] = 1
                break
        else:
            dp[node][0] = 1

N = int(input())
graph = [[] for _ in range(N+1)]


for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
visited = [False]*(N+1)
dp = [[0]*2 for _ in range(N+1)]
dfs(1)

answer = min(list(map(sum,list(zip(*dp)))))
print(answer)

string = input()
duck = 'quack'
cnt = 0
result = []
answer = 0
for st in string:
    flag = True
    for ind in range(len(result)):
        if duck[(duck.index(result[ind][-1])+1)%5] == st:
            result[ind].append(st)
            flag = False
            break

    if flag:
        if st != 'q':
            answer = -1
            break
        result.append([st])

if answer == -1:
    print(answer)
else:
    for i in result:
        if len(i)%5 != 0:
            print(-1)
            break
    else:
        print(len(result))

    

S = input()

duck = {'q':0,'u':1,'a':2,'c':3,'k':4}

queue = []
answer = 0
for sound in S:
    flag = True
    for ind in range(len(queue)):
        if (queue[ind] + 1)%5 == duck[sound]:
            queue[ind] = (queue[ind] + 1)%5
            flag = False
            break
    if flag:
        if duck[sound] != 0:
            answer = -1
            break
        queue.append(0)


if answer == -1:
    print(-1)
else:
    for num in queue:
        if num != 4:
            print(-1)
            break
    else:
        print(len(queue))

N = int(input())
arr = list(map(int,input().split()))

LIS = [arr[0]]
for i in range(1,len(arr)):
    if arr[i] > LIS[-1]:
        LIS.append(arr[i])
    else:
        start = 0
        end = len(LIS)
        idx = len(LIS)-1
        while start < end:
            mid = (start+end)//2
            if LIS[mid] >= arr[i]:
                idx = min(idx,mid)
                end = mid
            else:
                start = mid + 1
        LIS[idx] = arr[i]

LIS_CNT = len(LIS)
print(LIS_CNT)

import sys
input = sys.stdin.readline
while True:
    N,M = map(int,input().split())
    if not N+M:
        break

    arr = [list(map(int,input().split())) for _ in range(N)]
    maze = [[0 for _ in range(M)] for _ in range(N)]
    for y in range(M):
        maze[0][y] = arr[0][y]
    for x in range(1,N):
        for y in range(M):
            if arr[x][y]:
                maze[x][y] = maze[x-1][y] + arr[x][y]

    result = 0

    for x in range(N):
        col_idx = 0
        stack = []
        while col_idx<M:
            if stack:
                if stack[-1] <= maze[x][col_idx]:
                    stack.append(maze[x][col_idx])
                    col_idx += 1
                else:
                    size_stack = len(stack)
                    min_value = stack[-1]
                    cu_idx = -1
                    for i in range(size_stack):
                        result = max(result,min_value*(i+1))
                        cu_idx -= 1
                        if abs(cu_idx)<=size_stack and min_value > stack[cu_idx]:
                            min_value = stack[cu_idx]
                    

                    if maze[x][col_idx]:
                        stack.append(maze[x][col_idx])
                    else:
                        stack.clear()
                    col_idx += 1

            else:
                if maze[x][col_idx]:
                    stack.append(maze[x][col_idx])
                col_idx += 1
        if stack:
            size_stack = len(stack)
            min_value = stack[-1]
            cu_idx = -1
            for i in range(size_stack):
                result = max(result,min_value*(i+1))
                cu_idx -= 1
                if abs(cu_idx)<=size_stack and min_value > stack[cu_idx]:
                    min_value = stack[cu_idx]

    print(result)

        

import sys
input = sys.stdin.readline

while True:
    N,M = map(int,input().split())

    arr = [[0] + list(map(int,input().split())) + [0] for i in range(N)]
    if N+M == 0:
        break
    for i in range(1,N):
        for j in range(1,M+1):
            if arr[i][j]:
                arr[i][j] = arr[i-1][j] + 1
    result = 0
    for i in range(N):
        stack = [0]
        for j in range(1,M+2):
            while stack and  arr[i][j] < arr[i][stack[-1]]:
                height = arr[i][stack[-1]]
                stack.pop()
                width = j-stack[-1] - 1
                result = max(result,height*width)
            stack.append(j)
    print(result)

N = int(input())

arr = list(map(int,input().split()))
dp = [*arr]
for i in range(len(arr)-1):
    for j in range(i+1,len(arr)):
        if arr[i]< arr[j]:
            dp[j] = max(dp[j],dp[i] + arr[j])

print(max(dp))