Cho mảng \(A\) gồm \(m\) phần tử (các phần tử được đánh số từ \(1\) đến \(m\)) và mảng \(B\) gồm \(n\) phần tử (các phần tử được đánh số từ \(1\) đến \(n\)), mỗi phần tử của hai mảng chỉ nhận một trong ba giá trị \(-1,0,1\). Tiến hành tạo bảng \(C\) kích thước \(m \times n\), trong đó phần tử \((i, j)\) nhận giá trị \(C[i][j] = A[i] \times B[j]\) với \(1 \leq i \leq m\) và \(1 \leq j \leq n\).

Một bảng con vuông kích thước \(s\) của bảng \(C\) có phần tử trái trên là \((x,y)\) và phần tử phải dưới là \((x+s-1,y+s-1)\) với \(1 \leq x \leq m - s + 1\) và \(1 \leq j \leq n - s + 1\) được gọi là bảng con vuông "cân bằng" nếu:

Các phần tử thuộc đường chéo chính đều nhận giá trị bằng \(1\). Cụ thể, các phần tử \((x, y),(x + 1, y + 1),\ldots,(x + s - 1, y + s - 1)\) có giá trị bằng \(1\). Tổng tắt các các phần tử trong bảng con vuông bằng \(0\). Yêu cầu: Cho hai mảng \(A\) và \(B\), đếm số bảng con vuông "cân bằng" trong bảng \(C\).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương \(m, n\);
• Dòng thứ hai gồm \(m\) số mô tả mảng \(A\);
• Dòng thứ ba gồm \(n\) số mô tả mảng \(B\).

Dữ liệu ra

• Gồm một dòng chứa một số là số bảng con vuông "cân bằng" trong bảng \(C\).

Scoring

• Subtask \(1\) (\(20\) điểm): \(m, n \leq 30\);
• Subtask \(2\) (\(30\) điểm): \(m, n \leq 300\);
• Subtask \(3\) (\(30\) điểm): \(m, n \leq 1000\);
• Subtask \(4\) (\(20\) điểm): \(m \times n \leq 5 \times 10^6\).

Input 1

3 4
1 -1 1
1 0 -1 1

Output 1

1

Note

Chi có duy nhất một bảng con vuông "cân bằng" là bảng con kích thước \(2\) có phần tử trái trên là \((2,3)\).