만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

두 탑

면접 대비

시간 제한1초메모리 제한128 MB

요약
두 탑의 꼭대기에서 블록을 가장 적게 빼내어 남은 두 탑의 높이를 같게 합니다.
난이도

쉬움10점 중 3점

유형
그리디, 투 포인터, 누적 합
정답자
아직 제출이 없습니다

문제

어린 Bajtek이 할아버지에게서 블록 세트를 받았다. 각 블록에는 정해진 높이가 있다. Bajtek은 블록을 위로 하나씩 쌓아 탑을 만든다. 그는 가진 블록을 모두 사용해 탑 두 개를 세웠다.

이제 그는 두 탑의 높이를 같게 만들려면 최소 몇 개의 블록을 치워야 하는지 궁금하다. 블록은 각 탑의 꼭대기에서만 치울 수 있고, 새 블록을 더할 수는 없다. 특히 한 탑의 블록을 모두 치우는 것도 가능하다. 두 탑에서 블록을 모두 치우면 두 높이가 모두 0이 되어 서로 같아진다.

입력

첫째 줄에 두 정수 nn, mm (1≤n,m≤1061 \le n, m \le 10^6)이 주어진다. 각각 첫 번째 탑과 두 번째 탑을 이루는 블록의 개수이다.

둘째 줄에 nn개의 정수 a1,a2,…,ana_1, a_2, \dots, a_n (1≤ai≤1091 \le a_i \le 10^9)이 주어진다. aia_i는 첫 번째 탑에서 아래에서 ii번째 블록의 높이이며, a1a_1이 맨 아래 블록, ana_n이 맨 위 블록이다.

셋째 줄에 mm개의 정수 b1,b2,…,bmb_1, b_2, \dots, b_m (1≤bi≤1091 \le b_i \le 10^9)이 주어진다. bib_i는 두 번째 탑에서 아래에서 ii번째 블록의 높이이며, b1b_1이 맨 아래 블록, bmb_m이 맨 위 블록이다.

출력

두 탑의 높이가 같아지도록 치워야 하는 블록의 최소 개수를 한 줄에 출력한다.

힌트

예제3

  1. 예제 1

    입력
    4 3
    2 2 1 2
    1 3 2
    
    예상 출력
    3
    
  2. 예제 2

    입력
    2 1
    1 2
    3
    
    예상 출력
    0
    
  3. 예제 3

    입력
    1 1
    5
    3
    
    예상 출력
    2