Մաքսիմիզացնել արդյունքը

MAXRES - Մաքսիմիզացնել արդյունքը

Տրված են ոչ բացասական ամբողջ թվերի n հավաքածուներ։ Խաղացողը սկսում է առաջին հավաքածուից և ամեն հերթական հավաքածուից ընտրում մեկ թիվ՝ այն պայմանով, որ ընտրված յուրաքանչյուր թիվ պետք է փոքր չլինի նախորդ ընտրածից։ Այլ կերպ ասած, խաղացողը i-րդ քայլին մեկ թիվ է ընտրում i-րդ հավաքածուից, և եթե նա i-րդ քայլին ընտրել է x թիվը, իսկ i+1 քայլին՝ y-ը, ապա x ≤ y: Խաղացողը հաղթում է, եթե կարողանում է վերջին հավաքածուից ընտրել թիվ և ստանում է վերջին ընտրած թվին հավասար միավոր։ Օգնեք խաղացողին մաքսիմիզացնել արդյունքը։
Որպես պատասխան պետք է արտածել առավելագույն միավորը, որը կարող է ստանալ խաղացողը։ Եթե խաղացողը չի կարող հաղթել, պետք է արտածել -1:

Մուտքային տվյալներ

Առաջին տողում տրված է հավաքածուների n (1 ≤ n ≤ 105) քանակը։ Հաջորդ n տողերից i-րդում տրված են m[i], a[i], b[i], q[i] և t[i] թվերը։ i-րդ հավաքածուին (x[i] հավաքածուին) պատկանող թվերը որոշվում են հետևյալ կերպ.
x[i][1] = t[i],
x[i][j] = (a[i] * x[i][j - 1] + b[i]) % q[i], եթե 2 ≤ j ≤ m[i]:
Երաշխավորվում է, որ m[i] ≥ 1,
1 ≤ a[i], b[i] < q[i] ≤ 109,
0 ≤ t[i] ≤ 109:

Ելքային տվյալներ

Անհրաժեշտ է արտածել մեկ թիվ՝ առավելագույն միավորը, որը կարող է ստանալ խաղացողը խաղի վերջում։ Եթե հաղացողը չի կարող հաղթել, անհրաժեշտ է արտածել -1:

Օրինակ

Մուտք #1՝
1
7 4 8 11 2

Ելք #1՝
10


Մուտք #2՝
1
1 10000003
7 4 8 11 2
3 1 7 8 7
1 999999999 999999999 1000000000 999999999

Ելք #2՝
999999999


Մուտք #3՝
2
4 2 3 43 6
3 1 5 7 4

Ելք #3՝
-1

Օրինակների բացատրություն

Երկրորդ օրինակում առաջին հավաքածուն կլինի՝
x[1][1] = 2,
x[1][2] = (4 * x[1][1] + 8) % 11 = 5,
x[1][3] = (4 * x[1][2] + 8) % 11 = 6,
x[1][4] = (4 * x[1][3] + 8) % 11 = 10,
x[1][5] = (4 * x[1][4] + 8) % 11 = 4,
x[1][6] = (4 * x[1][5] + 8) % 11 = 2,
x[1][7] = (4 * x[1][6] + 8) % 11 = 5:
Երկրորդ հավաքածուն կլինի՝
x[2][1] = 7,
x[2][2] = (1 * x[2][1] + 7) % 8 = 6,
x[2][3] = (1 * x[2][2] + 7) % 8 = 5:
Իսկ երրորդ հավաքածուն ունի մեկ տարր՝ 999999999: Խաղացողը հավաքածուներից կարող է ընտրել համապատասխանաբար 6, 7, 999999999 թվերը, և արդյունքում կստանա 999999999 միավոր։
 
 
Աղբյուրը՝ Մարզային 2021
 

Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in