Coding 공부

N,M = map(int,input().split())
arr =  [ int(input()) for _ in range(N)]
left = max(arr)
right = 100000001
answer = float('inf')
while left<=right:
    mid = (left+right)//2
    temp = mid
    cnt = 1
    for num in arr:
        if temp >= num:
            temp -= num
        else:
            temp = mid - num
            cnt += 1
    
    if cnt >M:
        left = mid + 1
    else:
        right = mid - 1
        answer = min(answer,mid)

print(answer)

N = int(input())
arr = [input() for _ in range(N)]

start = 0
end = N-1

result = []

while start <= end:
    if arr[start] < arr[end]:
        result.append(arr[start])
        start += 1
    elif arr[start] > arr[end]:
        result.append(arr[end])
        end -= 1
    else:
        next_start = start
        next_end = end
        flag = True
        while arr[next_end] == arr[next_start]:
            if next_end >0:
                next_end -= 1
            if next_start < N:
                next_start += 1
            if arr[next_start] < arr[next_end]:
                flag = True
            elif arr[next_start] > arr[next_end]:
                flag = False

        if flag:
            result.append(arr[start])
            start += 1
        else:
            result.append(arr[end])
            end -= 1




lens = len(result)

if lens <= 80:
    print(''.join(result))
else:
    for ind in range(lens//80+1):
        if ind == lens//80:
            print(''.join(result[ind*80:]))
        else:
            print(''.join(result[ind*80:(ind+1)*80]))

from collections import deque

def bfs(node):
    stack = deque()
    stack.append(node)

    while stack:
        node = stack.popleft()

        for next_node in graph[node]:
            if visited[next_node] == -1:
                visited[next_node] = visited[node] + 1

                stack.append(next_node)



N, M = map(int,input().split())
INF = float('inf')
visited = [-1]*(N+1)


visited[1] = 0

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


for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
bfs(1)

max_value = max(visited)
max_ind = -1
for k in range(1,N+1):
    if visited[k] == max_value:
        max_ind = k
        break
print(max_ind,max_value,visited.count(max_value))

import sys
from collections import deque
input = sys.stdin.readline

for _ in range(int(input())):
    M,N = map(int,input().split())
    arr = []
    sange = []
    fire_set = set()
    visited = [[True]*M for _ in range(N)]
    for x in range(N):
        input_list = list(input().strip())
        for y in range(M):
            if input_list[y] == '*':
                fire_set.add((x,y))
            elif input_list[y] == '@':
                sange.append((x,y))
                visited[x][y] = False
                input_list[y] = '.'
        arr.append(input_list)
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    times = 0
    result = 'IMPOSSIBLE'
    flag = False
    while sange:
        new_sange = []
        new_fire = set()
        for fire in fire_set:
            for i in range(4):
                nx = fire[0] + dx[i]
                ny = fire[1] + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if arr[nx][ny] == '.':
                        new_fire.add((nx,ny))
                        arr[nx][ny] = '*'
        for sa in sange:
            for i in range(4):
                nx = sa[0] + dx[i]
                ny = sa[1] + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if visited[nx][ny] and arr[nx][ny] == '.':
                        new_sange.append((nx,ny))
                        visited[nx][ny] = False
                else:
                    result = times+1
                    flag = True
                    break
        if flag:
            break
        times += 1
        sange = new_sange[:]
        fire_set = new_fire

    print(result)
                

import sys
from collections import deque
input = sys.stdin.readline

def bfs(stack):
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while stack:
        x,y = stack.popleft()
        flag = visited[x][y] if visited[x][y] != 'FIRE' else 'FIRE'
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if visited[nx][ny] == -1 and (arr[nx][ny] == '.' or arr[nx][ny] == '@'):
                    if flag == 'FIRE':
                        visited[nx][ny] = flag
                    else:
                        visited[nx][ny] = flag + 1
                    stack.append((nx,ny))
            else:
                if flag != 'FIRE':
                    return flag + 1
    return 'IMPOSSIBLE'





for _ in range(int(input())):
    M,N = map(int,input().split())
    stack = deque()
    arr = []
    visited = [[-1]*M for _ in range(N)]
    for x in range(N):
        input_list = input()
        for y in range(M):
            if input_list[y] == '*':
                stack.append((x,y))
                visited[x][y] = 'FIRE'
            elif input_list[y] == '@':
                start = (x,y)
                visited[x][y] = 0
        arr.append(input_list)
    stack.append(start)
    print(bfs(stack))

import sys
input = sys.stdin.readline
def union_find(x,y):
    a = find_parent(x)
    b = find_parent(y)
    if a != b:
        make_set[b] = a
        friend_cnt[a] += friend_cnt[b]

    return a

def find_parent(A):
    if make_set[A] == A:
        return A
    make_set[A] = find_parent(make_set[A])
    return make_set[A]


T = int(input())

for tc in range(T):
    F = int(input())
    person_dict = {}
    cnt = 1
    make_set = [k for k in range(F*2+1)]
    friend_cnt = [1 for k in range(F*2+1)]
    for _ in range(F):
        x,y = input().split()
        if x not in person_dict:
            person_dict[x] = cnt
            friend_cnt[person_dict[x]] = 1
            cnt += 1
        if person_dict.get(y) == None:
            person_dict[y] = cnt
            friend_cnt[person_dict[y]] = 1
            cnt += 1
        x_num = person_dict[x]
        y_num = person_dict[y]
        k = union_find(x_num,y_num)
        print(friend_cnt[k])

def find_brackt():
    for ind,command in enumerate(commands):
        if command == '[':
            bracket.append((ind,1))
        elif command == ']':
            bracket.append((ind,-1))
    brind = 0
    temp = []
    while brind < len(bracket): 
        if bracket[brind][1] == 1:
            temp.append(bracket[brind][0])
        else:
            open_bracket = temp.pop()
            bracket_couple[bracket[brind][0]] = open_bracket
            bracket_couple[open_bracket] = bracket[brind][0]
        brind += 1

def go():
    global command_index,string_index,pointer
    if commands[command_index] == '-':
        arr[pointer] = arr[pointer]-1
        if arr[pointer]<0:
            arr[pointer] = 255
    elif commands[command_index] == '+':
        arr[pointer] = arr[pointer] + 1
        if arr[pointer] > 255:
            arr[pointer] = 0
    elif commands[command_index] == '<':
        pointer -= 1
        if pointer < 0:
            pointer = memorysize -1
    elif commands[command_index] == '>':
        pointer += 1
        if pointer == memorysize:
            pointer = 0
    elif commands[command_index] == '[':
        if arr[pointer] == 0:
            command_index = bracket_couple[command_index]
    elif commands[command_index] == ']':
        if arr[pointer] != 0:
            command_index = bracket_couple[command_index]
    elif commands[command_index] == '.':
        pass
    else:
        if string_index == inputsize:
            arr[pointer] = 255
        else:
            arr[pointer] = ord(strings[string_index])
            string_index += 1
    command_index += 1

T = int(input())
MAX_NUMBER = 50000000
for tc in range(T):
    memorysize,codesize,inputsize = map(int,input().split())
    pointer = 0 # 포인터가 가리키는 index
    arr = [0]*memorysize
    command_cnt = 0  # 명령 횟수
    commands = list(input())
    strings = list(input())
    command_index = 0  # 명령어의 위치
    string_index = 0
    result = 'Terminates'
    bracket = []
    bracket_couple = {}
    find_brackt()
    loop_flag = False
    loop_idx = float('inf')
    while command_cnt <= MAX_NUMBER and command_index < codesize:
        command_cnt += 1
        go()
    if command_index == codesize:
        print('Terminates')
    else:
        while command_cnt >=0:
            command_cnt -= 1
            go()
            loop_idx = min(command_index,loop_idx)
        print(f'Loops {loop_idx-1} {bracket_couple[loop_idx-1]}')

def find_brackt():
    for ind,command in enumerate(commands):
        if command == '[':
            bracket.append((ind,1))
        elif command == ']':
            bracket.append((ind,-1))
    brind = 0
    temp = []
    while brind < len(bracket): 
        if bracket[brind][1] == 1:
            temp.append(bracket[brind][0])
        else:
            open_bracket = temp.pop()
            bracket_couple[bracket[brind][0]] = open_bracket
            bracket_couple[open_bracket] = bracket[brind][0]
        brind += 1



T = int(input())
MAX_NUMBER = 50000000
for tc in range(T):
    memorysize,codesize,inputsize = map(int,input().split())
    pointer = 0 # 포인터가 가리키는 index
    arr = [0]*memorysize
    command_cnt = 0  # 명령 횟수
    commands = list(input())
    strings = list(input())
    command_index = 0  # 명령어의 위치
    string_index = 0
    result = 'Terminates'
    bracket = []
    bracket_couple = {}
    find_brackt()
    loop_flag = False
    loop_idx = float('inf')
    while command_index < codesize:
        if commands[command_index] == '-':
            arr[pointer] = (arr[pointer]-1)%(2**8)
        elif commands[command_index] == '+':
            arr[pointer] = (arr[pointer]+1)%(2**8)
        elif commands[command_index] == '<':
            pointer -= 1
            if pointer < 0:
                pointer = memorysize -1
        elif commands[command_index] == '>':
            pointer += 1
            if pointer == memorysize:
                pointer = 0
        elif commands[command_index] == '[':
            if arr[pointer] == 0:
                command_index = bracket_couple[command_index]
        elif commands[command_index] == ']':
            if arr[pointer] != 0:
                command_index = bracket_couple[command_index]
        elif commands[command_index] == '.':
            pass
        else:
            if string_index == inputsize:
                arr[pointer] = 255
            else:
                arr[pointer] = ord(strings[string_index])
                string_index += 1
        command_index += 1
        command_cnt += 1
        if command_cnt > MAX_NUMBER:
            loop_idx = min(loop_idx,command_index)
        if command_cnt > MAX_NUMBER*2:
            loop_flag = True
            break
    
    if loop_flag:
        print(f'Loops {loop_idx-1} {bracket_couple[loop_idx-1]}')
    else:
        print('Terminates')

import sys

input = sys.stdin.readline

T = int(input())

def find_parents(node):
    parent_list = [node]

    while parent_num[node] != -1:
        parent = parent_num[node]
        parent_list.append(parent)
        node = parent

    return parent_list



for _ in range(T):
    N = int(input())
    parent_num = [-1]*(N+1) # 해당 index의 부모가 안에 들어가 있다.
    for _ in range(N-1):
        parent,child = map(int,input().split())
        parent_num[child] = parent


    num1,num2 = map(int,input().split())

    parents1 = find_parents(num1)
    parents2 = find_parents(num2)

    if len(parents1) < len(parents2):
        parents1,parents2 = parents2, parents1
    result = -1
    for num in parents1:
        if num in parents2:
            result = num
            break
    print(result)

def check(number):
    remain_person = M

    for k in time_list:
        remain_person = remain_person - number//k
        if remain_person <=0:
            return -1
    return 1


N,M = map(int,input().split())
time_list = [int(input()) for _ in range(N)]

start = 1
end = ((M//N)+1)*max(time_list)
while start<end:
    mid = (start+end)//2
    remain_person = check(mid)

    if remain_person > 0:
        start = mid + 1
    else:
        end = mid -1
print(end)