Can you cast the spell? In Magic: the Gathering, mages (known as "planeswalkers") battle each other by casting spells. Spells cost mana. Five colors of mana exist: White, Blue, Black, Red, and Green, represented as {W}, {U}, {B}, {R}, and {G}, respectively.

A spell's cost is slightly more complex. The cost can be any combination of the following:


One or more colors
One or more colorless, represented as {X}, where X is a positive integer
One or more hybrids, represented as {Y/Z}, where Y and Z are either a color (represented by one of the five letters) or colorless, represented by a positive integer


The following rules apply when attempting to cast a spell:


A color in a cost must be satisfied by one mana of that color
A colorless cost {X} may be satisfied by X mana of any color
A hybrid cost {Y/Z} may be satisfied by satisfying either Y or Z

Note that braces are not nested
Y and Z are not hybrid



Write a program or function that, given a pool of mana and a cost, prints or returns true (or some truthy value) if and only if the mana in that pool can satisfy the cost, else false (or some falsy value).

A mana pool is a non-empty string of the format:

Color1,Color2,Color3,...,Colorn-1,Colorn

A cost is a non-empty string of the format:

Cost1,Cost2,Cost3,...,Costn-1,Costn

Examples

In the format Pool Cost -&gt; ExpectedOutput (with a space between Pool and Cost):

{R},{R},{G},{B},{R} {4},{R} -&gt; True
{G},{G},{G},{G},{W},{W},{W} {2/W},{2/U},{2/B},{2/R},{2/G} -&gt; False
{G},{G},{R} {R/G},{G/B},{B/R} -&gt; True
{R},{R},{R},{G} {1},{G},{2/G}-&gt; True
{R} {R},{R},{R},{R},{R} -&gt; False
{W},{R},{R} {2/W},{W/B} -&gt; True
{U},{U} {1} -&gt; True
{W},{R},{G} {1},{2} -&gt; True
Pyth, 55 53 52 50 bytes

FN*Fmsm?k}kG^Gvkcd\/ceKc-rz0`Hd\,#=sN)I!.-NhK1B)E0


Try it online: Demonstration or Test harness

Notice that the time and memory complexity is really bad. So the second example doesn't work. I allocates about 1.6 GB of Ram before it crashes on my machine. 

Explanation

The explanation is for the 53 solution. The only difference is, that the initial parsing happens in the middle instead of the beginning. 

Kc-rz0"{}"dFN*Fmsm?k}kG^Gvkcd\/ceKc-rz0`H\,#=sN)I!.-NhK1B)E0


So here's the initial parsing. 

Kc-rz0`Hd
   rz0     convert input() to lowercase
  -   `H   remove all curly brackets (`H = "{}")
 c      d  split at the space
K          assign to K


So the input "{W},{R},{R} {2/W},{W/B}" gets converted into ['w,r,r', '2/w,w/b']. 

m               ceK\,    map each cost d of the costs split by "," to:
 s                         the sum of
  m         cd\/           map each value k of cost split by "/" to:
    k                        k
   ? }kG                     if k in "abcdef...xyz" else
        ^Gvk                 Cartesian product with "abc...yz" of int(k) repeats


So what does this do? The cost input '2/w,w/b' gets converted into:

[['aa', 'ab', 'ac', ..., 'zx', 'zy', 'zz', 'w'], 'wb']


Every string in ['aa', 'ab', 'ac', ..., 'zx', 'zy', 'zz', 'w'] satisfies {2/W} and every char in 'wb' satisfies {w/b}. 

Now we generate the Cartesian product of these lists (or strings) and see, if any combination can be produced with the mana-pool. 

FN*F...              )      for N in Cartesian product of ...:
       #   )                   while 1:
        =sN                      N = sum(N)
                               this flattens N
            I!.-NhK            if not (subtract mana pool from N):
                   1             print 1 (True)
                    B            break
                      E      else:
                       0       print 0 (False)