#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class TheAirTripDivOne { public:
struct edge {
int to;
LL F, T, P;
};
int find(int n, vector <string> flights, int time)
{
vector< vector<edge> > e(n);
{
string input = accumulate(flights.begin(), flights.end(), string(""));
stringstream sin(input);
for(string line; sin>>line;) {
stringstream sin(line);
int a,b; LL f,t,p; char _;
sin >> a >> _ >> b >> _ >> f >> _ >> t >> _ >> p;
edge eg = {b-1,f,t,p};
e[a-1].push_back(eg);
}
}
int lf=0, ri=1000000001;
while( ri-lf>1 )
{
int c = (lf+ri)/2;
(ok(n,e,c,time) ? lf : ri) = c;
}
return lf ? lf : -1;
}
bool ok(int n, vector< vector<edge> >& e, LL transfer, LL TL)
{
typedef int vert;
typedef LL cost;
typedef pair<cost,int> cedge;
priority_queue<cedge, vector<cedge>, greater<cedge> > Q;
set<vert> V;
Q.push( cedge(0,0) );
while( !Q.empty() )
{
cost c = Q.top().first;
vert v = Q.top().second;
Q.pop();
if( V.count(v) )
continue;
if( v == n-1 )
return true;
V.insert(v);
vector<edge>& ne = e[v];
for(int i=0; i<ne.size(); ++i)
{
vert u = ne[i].to;
LL F=ne[i].F, T=ne[i].T, P=ne[i].P;
LL t = nextTime(c, F, P, v==0 ? 0 : transfer);
// cerr<<c<<" "<<F<<" "<<P<<" "<<transfer<<" !! "<<t<<endl;
if( !V.count(u) && t+T<=TL )
Q.push( cedge(t+T, u) );
}
}
return false;
}
LL nextTime(LL cur, LL F, LL P, LL transfer)
{
cur += transfer;
if( cur <= F )
return F;
return (cur-F)%P==0 ? cur : ((cur-F)/P+1)*P+F;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, TheAirTripDivOne().find(n, flights, time));}
int main(){
CASE(0)
int n = 3;
string flights_[] = {"1,2,1,4,7 ", "2,3,9,1,10"};
vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
int time = 20;
int _ = 14;
END
CASE(1)
int n = 3;
string flights_[] = {"1,2,1,1,1 2,3,2,1,98"};
vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
int time = 100;
int _ = -1;
END
CASE(2)
int n = 477;
string flights_[] = {"47,74,1,1,1"};
vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
int time = 20;
int _ = -1;
END
CASE(3)
int n = 7;
string flights_[] = {"1,3,15,17,11 1,3,14,16,14 5,7,12,18,18 1,6,13,1",
"6,12 1,2,18,14,13 5,6,10,10,18 3,1,10,10,10 1,3",
",17,16,10 2,3,16,18,16 6,1,15,12,10 2,1,15,18,1",
"0 4,7,10,16,15 6,3,10,14,10 1,6,19,19,15 1,4,12",
",10,14 4,7,10,18,14 2,3,16,12,12 1,3,14,10,19 3",
",7,17,10,12 2,1,14,12,16 4,3,19,11,12 1,6,10,18",
",12 2,3,16,12,10 6,2,10,18,12 5,1,14,18,12 5,1,",
"18,10,10 3,2,19,15,10 7,4,16,19,14 6,3,16,12,10",
" 5,7,14,13,13 1,3,12,10,16 5,7,16,18,15 6,2,18,",
"12,14 3,2,10,18,16 4,2,18,18,14 1,5,10,18,16 2,",
"3,10,19,16 1,4,11,18,15 2,1,15,15,14 7,2,10,12,",
"10"};
vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
int time = 74;
int _ = 33;
END
CASE(4)
int n = 7;
string flights_[] = {"1,4,10,8,2 4,6,14,8,2 6,2,8,1",
"0,1 2,7,19,5,1 ",
"1,5,15,17,11 5,3,10,1",
"0,18 3,7,12,18,18"};
vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
int time = 147;
int _ = 35;
END
/*
CASE(5)
int n = ;
string flights_[] = ;
vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
int time = ;
int _ = ;
END
CASE(6)
int n = ;
string flights_[] = ;
vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
int time = ;
int _ = ;
END
*/
}
// END CUT HERE