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.
Input
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.
Output
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.