5교시: 과학

추가 시간 및 메모리가 없습니다. 이 점에 유의하시기 바랍니다.

짐비는 과학 시간에 여러 실험을 합니다. 오늘 짐비는 몇 가지 물체를 가지고, 길이가 정확히 $10\,000$cm인 자를 이용해 평형을 맞추려 합니다. 자의 왼쪽 끝은 $0$cm 지점, 자의 오른쪽 끝은 $10\,000$cm 지점입니다. 짐비는 자의 $5\,000$cm 지점을 중심점으로 삼아 양쪽에 물체들을 올려놓으려고 합니다. 목표는 자의 양쪽에 있는 물체들이 중심점에서 생성하는 돌림힘이 평형을 이루도록 하는 것입니다.

돌림힘은 자의 중심점을 기준으로 왼쪽과 오른쪽에 있는 물체들이 각각 자에 작용하는 힘을 의미합니다. 중심점의 왼쪽에 놓인 물체는 반시계 방향으로, 오른쪽에 놓인 물체는 시계방향으로 돌림힘을 생성합니다. 돌림힘의 크기는 물체의 무게와 중심점까지의 거리의 곱으로 정의됩니다.

각 물체를 배치할 수 있는 위치는 미리 정해져 있으며, 같은 위치에 여러 개의 물체를 놓을 수 없습니다. 또한 자에 하나 이상의 물체를 올려놓아야 합니다. 각 물체를 해당 위치에 놓을지 말지 선택하여, 생성되는 반시계 방향 돌림힘의 크기의 합과 시계방향 돌림힘의 크기의 합이 같아지도록 하는 배치 방법이 몇 가지인지 구하세요.

첫 번째 줄에 물체의 개수를 나타내는 정수 $N$이 주어집니다. $(1 \leq N \leq 40)$

두 번째 줄에 물체의 무게를 나타내는 $N$개의 정수 $W_1, W_2,\cdots, W_N$가 공백을 간격으로 주어집니다. $(1 \leq W_i \leq 10^5)$

세 번째 줄에 $i$번째 물체를 올려놓을 수 있는 지점을 나타내는 $N$개의 정수 $P_1,$ $P_2,$ $\cdots,$ $P_N$이 공백을 간격으로 주어집니다. 이는 $i$번째 물체가 $P_i$cm 지점에 놓이는 것을 의미합니다. 물체가 $5\,000$cm 지점에 놓이는 경우는 주어지지 않습니다. $(0 \leq P_i \leq 10\,000;$ $P_i\ne5\,000)$

문제에서 요구하는 값을 첫 번째 줄에 출력해 주세요.