5

Time limit5sMemory limit555 MB

Summary

Given an array of non-negative integers with sum S and at least S/5 ones, count the pairs (k, T) where some subsequence of length k sums to T.

Level: Hard8 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

You are given an array $a$ of length $n$ consisting of non-negative integers. Calculate the number of pairs $(k, T)$ such that there exists a subsequence of $a$ of length $k$ whose sum is equal to $T$ . Just kidding, this is too general. Suppose the sum of elements of $a$ is equal to $S$ . Then it is guaranteed that $a$ has at least $S/5$ elements equal to $1$ .

Input

The first line contains two positive integers $n$ and $S$ ( $1 \le n, S \le 2 \cdot 10^5$ ), the number of elements in $a$ and their sum. The second line contains the array $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le S$ ). It is guaranteed that $\sum_{i=1}^{n} a_i = S$ and at least $S/5$ elements of $a$ are equal to $1$ .

Output

Print the number of pairs $(k, T)$ such that there exists a subsequence of $a$ of length $k$ whose sum is equal to $T$ .

Examples4

Example 1
Input
```
7 9
0 0 0 1 1 2 5
```
Expected output
```
42
```
Example 2
Input
```
10 33
9 9 8 1 1 1 1 1 1 1
```
Expected output
```
48
```
Example 3
Input
```
10 14
2 4 4 1 0 1 0 1 0 1
```
Expected output
```
81
```
Example 4
Input
```
10 14
3 5 3 0 1 0 1 0 1 0
```
Expected output
```
87
```