# The Morning Commute Codechef Solution

The Chef commutes to work every day using the city’s underground metro. The schedule for the trains has recently been changed and he wants to know how long it will take to travel from the station nearest to his house and the station nearest to his restaurant.

The Chef doesn’t want to change the route he took before, so he simply has to find out how long it will take to reach his restaurant along his usual route. This route is given by a sequence of stations s0, s1, …, sn where s0 is the station where the Chef enters the metro and sn is the station where the Chef exits the metro.

Trains are scheduled to run between every two consecutive stations si-1 and si. Such a schedule is specified by three integers xi, li, and fi. This means that the first train on this line starts operating at time xi. The time it takes this train to travel from si-1 and si is exactly li units. Finally, a train departs from station si-1 every fi minutes following the previous train. That is, a train departs at time xi, xi+fi, xi+2fi, and so on.

The Chef is very experienced at navigating the metro so the time it takes him to transfer between trains at a given station is essentially zero. Thus, if the Chef arrives at a station, say si, the moment that the train from si to si+1 is scheduled to depart, he skillfully hops on this next train. However, if the Chef arrives when no train to si+1 is scheduled to depart, he must wait until the scheduled departure time.

Help the Chef figure out how long it will take him to travel from station s0 to station sn. You may assume that the Chef is already at station s0 at time 0.

### Input

The first line consists of a single integer denoting the number of test cases (at most 50). Each test case begins with a line containing a single integer n between 1 and 1000 indicating the number of lines the Chef must traverse (so there are n+1 stations s0, s1, …, sn). The next n lines describe the train schedules between stations, one per line. The i’th such line gives the values xi, li, and fi for the train that travels between stations si-1 and si.

The xi values will be between 0 and 1000 and the li and fi values will be between 1 and 1000.

### Output

For each test case you are to output a single integer denoting the minimum time t for which the Chef can reach station sn using the given route. Remember, the Chef starts at s0 at time 0.

### Example

```Input:
3
2
0 4 7
0 6 5
2
0 1 2
6 2 10
2
1 2 3
0 2 3

Output:
11
8
5```

## The Morning Commute   – CodeChef Solution in JAVA

```import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{

try
{

Scanner sc=new Scanner(System.in);

int t=sc.nextInt();

while(t-->0)
{
int n;

n=sc.nextInt();

int x[]=new int[n];
int l[]=new int[n];
int f[]=new int[n];

int i;

int a,b,c;

for(i=0;i<n;i++)
{
a=sc.nextInt();
b=sc.nextInt();
c=sc.nextInt();
x[i]=a;
l[i]=b;
f[i]=c;
}

int time=0;

i=0;

int y=0;
while(i<n)
{
if(time<=x[i])
{
time=x[i]+l[i];
i++;

}
else
{
if((time-x[i])%f[i]==0)
{
time+=l[i];

}
else
{
y=(time-x[i])/f[i];

y++;

y=x[i]+y*f[i];

time=y+l[i];
}
i++;
}

}

System.out.print(time);
System.out.print("\n");
}

}
catch(Exception ee)
{

}

}
}
```

## The Morning Commute- CodeChef Solution in CPP

```#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
int t;
int x,l,f,n;
cin>>t;
while(t--){
cin>>n;
cin>>x>>l>>f;
ll ans=x+l;
for(int i=1;i<n;i++){
cin>>x>>l>>f;
if(x<ans){
ll tmp=(ll)((ans-x)/f);
if(((ans-x)%f)!=0){
tmp++;
}
x+=(f*tmp);
}
ans=x+l;
}
cout<<ans<<endl;
}

return 0;
}
```

## The Morning Commute -CodeChef Solution in Python

```t=int(input())
ans=[]
for _ in range(t):
n=int(input())
schedule=[]
for i in range(n):
l=list(map(int,input().split()))
schedule.append(l)
time=schedule+schedule
for i in range(1,len(schedule)):
if time<schedule[i]:
time+=((schedule[i]-time)+schedule[i])
elif time==schedule[i]:
time+=schedule[i]
else:
if (time-schedule[i])%schedule[i]==0:
time+=schedule[i]
else:
wait=((time-schedule[i])%schedule[i])
time+=(schedule[i]-wait)+schedule[i]
ans.append(time)
for _ in ans:
print(_)
```

Disclaimer: The above Problem (The Morning Commute) is generated by CodeChef but the solution is provided by Codeworld19.This tutorial is only for Educational and Learning purpose.