// Problem         : Tarot Knight (NAIPC 2019)
// Author          : Darcy Best
// Expected Result : AC
// Complexity      : O( n * G * (log(G) + log(MAX)) ), where G is the number
//                   of distinct GCD of subsets of a,b and MAX is the
//                   largest a,b.

// The state from one card is either a lattice or checkerboard.
// Combining two cards also gives this property. Graph is a DAG.
// Find shortest path to a state that has (0,0) on using DP.

#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <functional>
#include <utility>
#include <algorithm>
#include <cassert>
using namespace std;

typedef pair<int,bool> pib;

int gcd(int a,int b){
  return b == 0 ? a : gcd(b, a%b);
}

int factors_of_2(int x){
  int ans = 0;
  for(;x % 2 == 0;x/=2) ans++;
  return ans;
}

struct TarotCard {
  int r,c,a,b,p;
  pib card_grid;
  
  void read(){
    cin >> r >> c >> a >> b >> p;
    card_grid.first  = gcd(a,b);
    card_grid.second = factors_of_2(a) == factors_of_2(b);
  }
  
  bool on_grid(const pib& grid) const{
    if(grid.first == 0) return r == 0 && c == 0;
    
    if(r % grid.first || c % grid.first) return false;
    if(!grid.second) return true;
    return (r / grid.first) % 2 == (c / grid.first) % 2;
  }
};

pib combine(const pib& grid1, const pib& grid2){
  int g1 = grid1.first * (grid1.second ? 2 : 1);
  int g2 = grid2.first * (grid2.second ? 2 : 1);
  int g = gcd(g1,g2);

  int r1 = grid1.first % g; if(r1 == 0) r1 += g;
  int r2 = grid2.first % g; if(r2 == 0) r2 += g;
  int r = min(r1,r2);
  
  return make_pair(r,r != g);
}

map<pib,long long> dist;

long long f(const vector<TarotCard>& A, const pib& t, const TarotCard& dest){
  if(dest.on_grid(t)) return 0;
  if(dist.count(t)) return dist[t];
  
  long long ans = -1;
  for(const TarotCard& c : A)
    if(c.on_grid(t)){
      pib now = combine(t,c.card_grid);
      if(now == t) continue;
      long long to_end = f(A,now,dest);
      if(to_end == -1) continue;
      if(ans == -1 || ans > c.p + to_end)
	ans = c.p + to_end;
    }
  return dist[t] = ans;
}

int main(){
  int n; cin >> n;

  vector<TarotCard> A(n);
  for(auto& x : A) x.read();

  TarotCard dest = { abs(A[0].r), abs(A[0].c) };
  
  for(int i=n-1;i>=0;i--){
    A[i].r = abs(A[i].r - A[0].r);
    A[i].c = abs(A[i].c - A[0].c);
  }

  cout << f(A,make_pair(0,false),dest) << endl;
}