시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 1024 MB 16 6 6 60.000%

문제

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

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

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

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

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

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

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

입력

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

둘째 줄에 N개의 정수 A1, A2, …, AN이 공백을 사이에 두고 주어진다.

셋째 줄에 M개의 정수 B1, B2, …, BM이 공백을 사이에 두고 주어진다.

출력

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

제한

  • 1 ≤ N, M ≤ 200,000
  • -109Ai ≤ 109 (1 ≤ iN)
  • -109Bi ≤ 109 (1 ≤ iM)

예제 입력 1

3 3
-1 0 1
-1 0 1

예제 출력 1

1

예제 입력 2

3 3
-1 0 1
1 0 1

예제 출력 2

5