If you get WA @ 3, please use 64-bit integers to avoid overflow.

If you get WA @ 5, the following testcase might help:
4 4
1 1 2
The answer is:
6
3 4
3 3
1 3
1 1
3 1
3 0

Good luck.