공산주의

시간 제한1초메모리 제한512 MB

요약

N개의 일을 세 사람에게 나누어 줄 때, Ad와 Larry가 받는 금액의 차이가 D 이하가 되도록 하는 배정의 수를 센다.

난이도: 어려움10점 중 8점
유형: 수학, 백트래킹, 동적 계획법, 완전 탐색
정답자: 아직 제출이 없습니다

문제

평화로운 린카루 마을에 일거리가 $N$ 개 있다. 이 일을 린카루, 아드, 래리 세 사람에게 나눠 주려고 한다. 일 하나는 세 사람 중 정확히 한 명이 맡는다.

아드와 래리는 공평함을 중시한다. 그래서 아드가 맡은 일의 보수 합과 래리가 맡은 일의 보수 합은 차이가 $D$ 를 넘으면 안 된다. 린카루가 받는 보수에는 조건이 없다.

어떤 일을 맡은 사람이 서로 다르면 두 분배 방법은 다른 방법이다. 일을 나누는 가짓수를 구하여라.

입력

첫째 줄에 일의 개수 $N$ 이 주어진다. 둘째 줄에 보수를 뜻하는 정수 $N$ 개 $A_1, \dots, A_N$ 이 공백을 사이에 두고 주어진다. 셋째 줄에 넘으면 안 되는 보수 합의 차이 $D$ 가 주어진다. ( $1 \le N \le 30$ , $1 \le A_i \le 10^{16}$ , $0 \le D \le 10^{18}$ )

출력

일을 나누는 서로 다른 방법의 수를 출력하여라.

예제2

예제 1
입력
```
3
1 2 3
1
```
예상 출력
```
9
```
예제 2
입력
```
3
1 2 3
0
```
예상 출력
```
3
```