SUBSUMS - Subset Sums

no tags 

Given a sequence of N (1 ≤ N ≤ 34) numbers S1, ..., SN (-20,000,000 ≤ Si ≤ 20,000,000), determine how many subsets of S (including the empty one) have a sum between A and B (-500,000,000 ≤ A ≤ B ≤ 500,000,000), inclusive.

Input

The first line of standard input contains the three integers N, A, and B. The following N lines contain S1 through SN, in order.

Output

Print a single integer to standard output representing the number of subsets satisfying the above property. Note that the answer may overflow a 32-bit integer.

Example

Input:
3 -1 2
1
-2
3

Output:
5

The following 5 subsets have a sum between -1 and 2:

  • 0 = 0 (the empty subset)
  • 1 = 1
  • 1 + (-2) = -1
  • -2 + 3 = 1
  • 1 + (-2) + 3 = 2

Added by:Neal Wu
Date:2009-01-19
Time limit:0.328s-0.657s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: ERL JS SCM chicken

hide comments
i_am_looser: 2015-05-24 16:58:18

Finally AC.............. ; )

prateek goyal: 2015-05-24 15:17:35

\m| 100th on spoj feeling relaxed :)

Rocker3011: 2015-02-13 03:30:19

finally did this problem, it took me 2 years of training to be able to solve it with ease, :)

ashish kumar: 2014-12-29 15:45:54

wrong ans on 15th testcase

Archit Jain: 2014-08-14 13:27:08

nice concept

selfcompiler: 2014-08-12 05:37:30

:D it gives TLE ,use Fast Fourier Transformation :)

innovolt: 2014-03-26 18:44:17

start from brute force and then small optimization,not too tough as it seems...

paras meena: 2014-02-15 20:19:28

I think weak Test cases =P

Rishav Goyal: 2014-02-05 22:20:23

really enjoyed !! while solving it !!

aqfaridi: 2014-01-24 19:03:47

nice..