It is a glorious day for the revolution! Or so it would have been.

Najenda, one of the generals of the empire, has decided to defect to the revolutionary cause, alongside the vast majority of her army. However, news of her defection was quickly picked up by Imperial soldiers, and her army was cut off and nearly destroyed by loyalists under General Esdeath. Fortunately, Najenda and a few of her soldiers managed to escape alive. Unfortunately, they are badly injured and are completely out of supplies.

To resupply Najenda, the high command of the revolutionary army has decided to air drop supplies into a mountain range, consisting of a row of \(N\) mountains. However, the revolutionary army does not wish to leave any traces for imperial scouts who could reveal Najenda’s location and cause her to be annihilated. They have estimated that for a supply drop to be well hidden on mountain \(i\), it must be dropped at an altitude \(s_i\) on that mountain such that

\[h_j-|i-j|^{\frac{a-1}{a}} \geq s_i\]

For all \(1 \leq j \leq N\) and \(j \neq i\), where \(h_i\) represents the height of the \(i\)th mountain, and \(a\) is a constant which depends on the scout in question who is expected to be on patrol.

Messengers have indicated that Najenda requires at least \(K\) supply drops. However, air dropping supplies is expensive. In fact, performing a supply drop on the \(i\)th mountain costs \(c_i\) gold coins, with an additional cost of \(v_i\) gold coins for each unit altitude lower than the mountain’s maximum height.

As head of the revolutionary army’s logistics corps, you are charged with finding the minimum cost of keeping Najenda supplied so that she can safely arrive at the revolutionary army’s headquarters. Since it is illogical to provide an absurdly large number of gold coins, you are asked to provide the cost in \(D\) gold bars and \(C\) gold coins, where a gold bar is equal to \(10^9\) gold coins. To save materials, you are also asked to minimize \(D+C\) in your final solution without increasing the cost.

Input Specification

The first line of input contains three space separated integers \(N\), \(K\), and \(a\): the number of mountains in the mountain range, the number of supply drops Najenda needs, and the scout constant.

The next \(N\) lines of input each contain one integer \(h_i\), the height of the \(i\)th mountain.

The next \(N\) lines of input each contain one integer \(c_i\), the flat cost of performing a supply drop on mountain \(i\).

The next \(N\) lines of input each contain one integer \(v_i\), the additional cost of dropping supplies per unit altitude lower than mountain \(i\)’s maximum height.

Output Specification

Two space separated integers: the required number of gold bars \(D\) and the required number of gold coins \(C\) to keep Najenda resupplied. Do not end with a trailing space.

Input Constraints

\(1 \leq h_i \leq 2\times 10^9\)

\(0 \leq c_i, v_i \leq 10^6\)

\(2 \leq a \leq 10\)

Subtask 1 (20%)

\(1 \leq K \leq N \leq 10^3\)

Subtask 2 (30%)

\(1 \leq K \leq N \leq 5 \times 10^4\)

\(a = 2\)

Subtask 3 (50%)

\(1 \leq K \leq N \leq 5 \times 10^5\)

It is guaranteed that at all \(N\) possible mountains, no supply drops have to be placed at a negative elevation.

Sample Input

3 2 2
10
9
11
2
5
1
5
4
0

Sample Output

0 6

Explanation

The maximum elevation we can place supplies at on mountain \(1\) is at elevation \(8\) due to the height of mountain \(2\) (\(9-|2-1|^{\frac{1}{2}} = 8)\). Likewise, the maximum elevation of a supply drop on mountain \(2\) is at elevation \(9\), and at elevation \(8\) for mountain \(3\). It costs \(2+5\cdot 2 = 12\) gold coins to perform a supply drop on mountain \(1\), \(5+0\cdot 4 = 5\) gold coins to perform a supply drop on mountain \(2\) and \(1+3\cdot 0 = 1\) gold coins to perform a supply drop on mountain \(3\). Since Najenda only requires \(2\) supply drops, we can perform a supply drop on mountains \(2\) and \(3\) for a total cost of \(0\) gold bars and \(6\) gold coins.