Solve the knapsack problem Knapsack Problem

(Actually, this is a subset of real knapsack problem.... - there's nothing to optimize!)

The knapsack problem is:


  Given positive integers , and an integer S, find non-negative integers  satisfies 


... or in (my bad) English...


  Suppose you have many stuffs which weights , find configurations of those stuffs which weights S.


Problem


  Find all configurations of stuffs, which information is given by input.


Input

You can make your own format, but you should enable users to input the sum of stuffs(S), weights of stuffs , and names of each stuffs.

Stuffs' name may contain [a-zA-Z0-9 _] (alphanumeric + _ + space).

You may assume that the input is correct,  are positive, and S is non-negative.

For example, consider this pseudo-real world situation, where a man orders appetizers worth exactly $15.05:



A possible input is:

1505
215 Mixed fruit
275 French fries
335 Side salad
355 Hot wings
420 Mozzarella sticks
580 Sampler plate


Output

Print all possible configurations (no same configurations, one configuration per one line, each line contains pairs of amount of a stuff and name of the stuff).

Stuff with zero amount can be omitted.

If there's no configuration possible, simply print X.

Example

Input and output format (and order) can be vary.

This is JS code I made roughly:

var s=prompt(),a=s.split('/'),b=[],c,i=1,t=a[0];while(i&lt;a.length){c=a[i].split(/^([^ ]*) /);c.shift();b.push(c);i++;}
var d=[],l=b.length,p=0,_=0;for(i=0;i&lt;l;i++)d[i]=0;
function as(x,y){for(var i=0,s=0;i&lt;x.length;i++)s+=x[i][0]*y[i];return s}
function cs(x,y){for(var i=0,s='';i&lt;x.length;i++)s+=y[i]+' '+x[i][1]+', ';return s}
while(p&gt;=0){
    p=0;
    while((q=as(b,d))&gt;=t){
        if(q==t){console.log(cs(b,d));_=1}
        d[p]=0;p++;if(p&gt;=l){p=-1;break;}
        d[p]++;
    }
    if(p==0) d[0]++;
}
if(!_) console.log('X');




Input

1505/215 Mixed fruit/275 French fries/335 Side salad/355 Hot wings/420 Mozzarella sticks/580 Sampler plate

Output 

7 Mixed fruit, 0 French fries, 0 Side salad, 0 Hot wings, 0 Mozzarella sticks, 0 Sampler plate, 
1 Mixed fruit, 0 French fries, 0 Side salad, 2 Hot wings, 0 Mozzarella sticks, 1 Sampler plate, 




Input

5/1 A/1 B/1 C

Output

5 A, 0 B, 0 C, 
4 A, 1 B, 0 C, 
3 A, 2 B, 0 C, 
2 A, 3 B, 0 C, 
1 A, 4 B, 0 C, 
0 A, 5 B, 0 C, 
4 A, 0 B, 1 C, 
3 A, 1 B, 1 C, 
2 A, 2 B, 1 C, 
1 A, 3 B, 1 C, 
0 A, 4 B, 1 C, 
3 A, 0 B, 2 C, 
2 A, 1 B, 2 C, 
1 A, 2 B, 2 C, 
0 A, 3 B, 2 C, 
2 A, 0 B, 3 C, 
1 A, 1 B, 3 C, 
0 A, 2 B, 3 C, 
1 A, 0 B, 4 C, 
0 A, 1 B, 4 C, 
0 A, 0 B, 5 C, 




Input

10/20 A/11 B

Output

X



Input

250/35 Portal 2/21 Minecraft/12 Braid

Output

5 Portal 2, 3 Minecraft, 1 Braid, 
2 Portal 2, 8 Minecraft, 1 Braid, 
2 Portal 2, 4 Minecraft, 8 Braid, 
2 Portal 2, 0 Minecraft, 15 Braid, 


Input

250/33 Portal 2/21 Minecraft/12 Braid

Output

X



Winner

Since this is the code golf game, person with shortest code win.

If two codes have same length, then a code with highest votes win.
Mathematica, 59 chars 

Tally/@IntegerPartitions[#1,All,#2/._[x_,_]-&gt;x]/.#2/.{}-&gt;X&amp;


Invoke with

%[1505, {215 -&gt; "MF", 275 -&gt; "FF", 335 -&gt; "SS", 355 -&gt; "HW", 420 -&gt; "MS", 580 -&gt; "SP"}]