Linear Functions

You are given an array with N non-negative integers. Initially, i.e. at time 0, the i-th value of the array is Ai. After t (t is a non-negative integer) time units, it will be increased by t*Bi.
You are also given N integers Pi, and the beauty of the array is simply defined as A1 mod P1 + A2 mod P2 + … + AN mod PN. The goal is to maximize the beauty of the array. You have T time units.
Your task is to calculate the maximum beauty of the array in T time units and when you can get the maximum beauty. More formally, you have to find the maximum value of (A1+t*B1) mod P1 + (A2+t*B2) mod P2 + … + (AN + t*BN) mod PN, where t is a non-negative integer in [0, T], and also t which gives maximum value.

There are multiple test cases. Please process till EOF (end of file).
The 1st line of each test case contains 2 integers N and T. In the 2nd line, there are N space-separated integers A1, A2, … , AN. The next line also contains N space-separated integers B1, B2, … , BN. Then the last line of each test case contains N space-separated integers P1, P2, … , PN.
1<=N, T<=100000.
For all i (1 <= i <= N), 0 <= Ai, Bi < Pi, 5*10^8 < Pi < 10^9.
For simplicity, all Pi are prime.
All Ai, Bi are randomly and uniformly generated between [0, Pi).
The sum of all N will not exceed 1000000.
The number of test cases is smaller than 250. Most test cases are small.
In at least 50% of cases, N will not exceed 100, at least 80% of cases, N will not exceed 1000.

For each test case, you have to print exactly 2 integers in one line, the maximum beauty and the time t in [0, T], which gives the maximum beauty. If there are multiple optimal t values then print the smallest one.

5 1
0 0 0 0 0
1 2 3 4 5
2 3 5 7 11

15 1

2019 Multi-University Training Contest 4