Linear Functions

Problem Description

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 tBi. 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+tB1) mod P1 + (A2+tB2) mod P2 + бн + (AN + tBN) 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.

Sample Input

5 1

0 0 0 0 0

1 2 3 4 5

2 3 5 7 11

Sample Output

15 1

Source

2019 Multi-University Training Contest 4