시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 31 7 6 75.000%

문제

$N$개의 조각으로 이뤄진 파인애플 피자 한 판이 있다. 각 피자 조각의 파인애플 토핑의 개수는 시계 방향 순으로 $a_1, a_2, \cdots, a_N$개다. 파인애플 피자를 맛보기 위해 $K(\le N)$명의 손님이 줄을 서서 기다리고 있다. 당신은 첫 조각을 고른 후, 시계 방향 순으로 피자를 한 조각씩 떼어 줄을 선 순서대로 손님에게 제공한다. 예를 들어, $4$명의 손님에게 토핑 개수가 $a_{N-1}$개, $a_N$개, $a_1$개, $a_2$개인 피자 조각을 순서대로 나눠줄 수 있다.

각 손님의 나이는 줄을 선 순서대로 $b_1, b_2, \cdots, b_K$이다. 손님들은 자신보다 나이가 어리거나 같은 사람보다 파인애플 토핑을 적게 받으면 그 자리에서 밥상을 엎어버린다.

손님들이 밥상을 엎지 않도록 피자 조각을 고를 수 있는 방법은 몇 가지일까?

입력

첫째 줄에 피자 조각의 개수 $N$과 손님의 수 $K$가 공백으로 구분되어 주어진다. ($1 \leq K \leq N \leq 100\ 000$)

둘째 줄에 각 피자 조각의 파인애플 토핑의 개수를 나타내는 정수 $a_1, a_2, \cdots, a_N$가 공백으로 구분되어 주어진다. ($0 \leq a_i \leq 10^9$)

셋째 줄에 손님들의 나이를 나타내는 정수 $b_1, b_2, \cdots, b_K$가 공백으로 구분되어 주어진다. ($0 \leq b_i \leq 10^9$)

출력

손님들이 밥상을 엎지 않도록 피자 조각을 고를 수 있는 방법의 수를 출력한다.

예제 입력 1

5 4
1 2 3 2 1
2 1 1 2

예제 출력 1

1

예제 입력 2

5 4
1 1 1 1 1
9 9 9 9

예제 출력 2

5

출처

University > 서강대학교 > 2020 Sogang Programming Contest (Champion) H번