19856번 - 계주 코스 정하기

승현이는 한 학교에서 선생님으로 근무하고 있다. 이번에 운동회를 담당하게 된 승현이는 릴레이 계주의 코스 중 하나를 어떻게 만들지 고심 중이다.

이 코스는 N행 M열의 구역으로 나뉜 공간에서 치러질 것이며, 위에서부터 i번째 행, 왼쪽에서부터 j번째 열의 구역은 (i, j)로 표현된다. 승현이는 1열의 한 구역을 시작 지점으로, M열의 한 구역을 도착 지점으로 하는 코스를 만들고자 한다. 이때, 도착 지점은 시작 지점보다 위쪽 구역은 아니어야 한다. 즉, 코스가 구역 (S, 1)에서 시작하여 (T, M)에서 끝난다고 할 때, 1 ≤ S ≤ T ≤ N가 성립해야 한다. 따라서 가능한 시작 지점과 도착 지점의 후보는 N(N+1)2가지가 존재한다.

학생들은 최단 경로로 도착 지점에 도달하고 싶어 하기 때문에, 시작 지점에서 출발하여 오른쪽이나 아래쪽으로 인접한 구역으로 이동하는 것만을 반복하여 도착 지점에 도달하고자 할 것이다.

승현이네 학교의 전통은 릴레이 계주에서 바통 대신 선인장을 들고 달리는 것이다. 그러나 선인장은 추위에 약하기 때문에, 만약 학생이 선인장을 들고 기온이 0도 미만인 곳을 지나가게 된다면 선인장은 시들고 만다. 이 릴레이 경주는 선인장이 시들면 탈락 처리되기 때문에, 학생들은 기온이 0도 이상인 구역만 지나가야 한다.

i행의 구역은 북서풍의 영향으로 A_i도의 영향을 받고, j열의 구역은 동남풍의 영향으로 B_j도의 영향을 받는다. 따라서, 구역 (i, j)의 기온은 (A_i + B_j)도이다.

시작 지점과 도착 지점이 정해졌을 때, 기온이 0도 이상인 구역만 지나면서 시작 지점부터 오른쪽 또는 아래쪽으로 인접한 구역으로 이동하는 것을 반복하여 도착 지점에 도달하는 것이 가능하다면 이 경우는 릴레이 계주 코스로 가능한 경우이다. 이때, 시작 지점과 도착 지점 역시 기온이 0도 이상이어야 한다.

N(N+1)2가지의 총 후보 중, 가능한 시작 지점과 도착 지점 쌍의 경우의 수를 구하여라.

첫 줄에 두 정수 N과 M이 공백을 사이에 두고 주어진다.

둘째 줄에 N개의 정수 A₁, A₂, …, A_N이 공백을 사이에 두고 주어진다.

셋째 줄에 M개의 정수 B₁, B₂, …, B_M이 공백을 사이에 두고 주어진다.

첫 줄에 가능한 코스의 개수, 즉 가능한 (시작 지점, 도착 지점) 쌍의 개수를 출력한다.

• 1 ≤ N, M ≤ 200,000
• -10⁹ ≤ A_i ≤ 10⁹ (1 ≤ i ≤ N)
• -10⁹ ≤ B_i ≤ 10⁹ (1 ≤ i ≤ M)