Problem Statement 
 The king has been out to work for a long time and he wants to go back to his queen as fast as possible. The king is in city 0 and the queen is in city N. There are roads and flights connecting city i to city (i+1) for all i between 0 and N1, inclusive.
The time it takes to travel from city i to city (i+1) by road and by flight is given by the ith elements of roadTime and flightTime, respectively. roadTime can be generated from the following pseudocode:
roadTime[0] = roadFirst mod roadMod;
for i = 1 to N1
roadTime[i] = (roadTime[i1]*roadProd + roadAdd) mod roadMod;
// note that (roadTime[i1]*roadProd + roadAdd) may overflow a 32bit integer
flightTime can be generated similarly by using flightFirst, flightProd, flightAdd, flightMod.
However, taking a flight risks the life of the king during takeoffs due to the technological limitations in the kingdom. Hence the queen has asked him to ensure that the total number of takeoffs during his entire journey does not exceed K.
To minimize the number of takeoffs, the king may choose to take a direct flight from city i to city i+j instead of separate flights from city i to city i+1, then from i+1 to i+2, ... and from i+(j1) to i+j. The time taken for this flight is the sum of the times taken for the flights from i to i+1, i+1 to i+2, ..., i+(j1) to i+j.
Return the minimum amount of time in which the king can reach his queen.


Definition 
 Class:  RoadOrFlightHard  Method:  minTime  Parameters:  int, int, int, int, int, int, int, int, int, int  Returns:  long  Method signature:  long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K)  (be sure your method is public) 




Constraints 
  N will be between 1 and 400000, inclusive. 
  roadFirst, roadAdd, flightFirst and flightAdd will each be between 0 and 100000, inclusive. 
  roadProd, roadMod, flightProd and flightMod will each be between 1 and 100000, inclusive. 
  K will be between 0 and 40, inclusive. 
  K will be less than or equal to N. 

Examples 
0)  
  Returns: 14  The pseudocode gives roadTime = {4, 6, 8} and flightTime = {1, 11, 4}. The fastest way to reach the queen is to take the road from city 0 to 1 and 1 to 2, and a flight from city 2 to 3. 


1)  
  Returns: 11  roadTime and flightTime are the same as in previous example. But now the king is allowed 2 takeoffs. 


2)  
  Returns: 12  roadTime = {4, 6, 8} and flightTime = {1, 7, 4}. Even though roadTime[1] < flightTime[1], it is best to take a direct flight from city 0 to city 3 which takes a total time of 1 + 7 + 4 = 12 units. 


3)  
 5  85739  94847  93893  98392  92840  93802  93830  92790  3 
 Returns: 122365  
