UVa 11259 - Coin Changing Again

This took lot of my time and I managed to come up with this Top-down Dynamic Programming solution. This approach times out. Any suggestions? Problem Statement : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2226

# include <cstdio>
# include <map>
# include <set>
using namespace std;
struct State
{
 State (int v1, int v2, int v3, int v4)
 {
  V1 = v1; V2 = v2; V3 = v3; V4 = v4;
 }
 int getPart2(int Value = 0)
 {
  int Part2 = 0;
  Part2 = (V4 >> 13);
  Part2 |= (Value << 4);
  return Part2;
 }
 unsigned long long getPart1()
 {
  unsigned long long Part1 = 0;
  Part1 = V1;
  Part1 |= (V2 << 17);
  Part1 |= ((unsigned long long)V3 << 34);
  Part1 |= ((unsigned long long)V4 << 51);
  return Part1;
 }
 int V1, V2, V3, V4;
};
map <int, set<unsigned long long> > States;
map <int, set<unsigned long long> > Solutions;
int c1, c2, c3, c4, q, d1, d2, d3, d4, v;
unsigned long long Result ;
bool CheckVisited (unsigned long long Part1, int Part2)
{
 if (States[Part2].count (Part1)) return true;
 States[Part2].insert (Part1);
 return false;
}
void Solution (State & s, int Value)
{
 unsigned long long Part1 = s.getPart1();
 int Part2 = s.getPart2(Value);
 if (!Value)
 {
  Solutions[Part2].insert (Part1);
  return;
 }
 if (CheckVisited(Part1, Part2)) return;
 if (s.V1 - 1 >= 0 && Value - c1 >= 0)
 {
  s.V1--;
  Solution (s, Value - c1);
  s.V1++;
 }
 if (s.V2 - 1 >= 0 && Value - c2 >= 0)
 {
  s.V2--;
  Solution (s, Value - c2);
  s.V2++;
 }
 if (s.V3 - 1 >= 0 && Value - c3 >= 0)
 {
  s.V3--;
  Solution (s, Value - c3);
  s.V3++;
 }
 if (s.V4 - 1 >= 0 && Value - c4 >= 0)
 {
  s.V4--;
  Solution (s, Value - c4);
  s.V4++;
 }
}
int main()
{
 freopen ("Input.txt", "r", stdin);
 freopen ("Scratch.txt", "w", stdout);
 int N;
 scanf ("%d", &N);
 State s (0, 0, 0, 0);
 while (N--)
 {
  scanf ("%d%d%d%d%d", &c1, &c2, &c3, &c4, &q);
  while (q--)
  {
   scanf ("%d%d%d%d%d", &s.V1, &s.V2, &s.V3, &s.V4, &v);
   Result = 0;
   States.clear();
   Solutions.clear();
   Solution (s, v);
   for (map<int, set<unsigned long long> >::iterator it = Solutions.begin(); it != Solutions.end(); it++)
    Result += it->second.size();
   printf ("%lld\n", Result);
  }
 }
}