Diamond Collection Achievement

Player Q, a casual gamer with impressive results in algorithm contests, is well known for his diamond collecting skills in a popular casual game. In the game, there are n types of diamonds numbered from \(1\) to \(n\). Q already owns \(a_i\) diamonds of type \(i\). Diamonds can only be obtained by purchasing them from the in‐game shop, and the price for type \(i\) diamond is \(b_i\) points. There is no limit on the number of diamonds you can buy; however, since the game does not allow discarding diamonds, you can only add to your collection.

Recently, a limited‐time achievement task was released. To earn the prestigious title, a player must meet the following requirement: Given two positive integers \(k\) and \(m\), for every integer \(x\) with \(x\ge 2^k\), the following sum must be a multiple of \(m\):

[ S(x)=a_{x}+a_{\lfloor\tfrac{x}{2}\rfloor}+a_{\lfloor\tfrac{x}{4}\rfloor}+a_{\lfloor\tfrac{x}{8}\rfloor}+\cdots+a_{\lfloor\tfrac{x}{2^k}\rfloor} \equiv 0 \pmod{m}. ]

Since Q cannot remove any diamonds he already owns, he may need to purchase additional diamonds to satisfy the above condition. For diamond type \(i\), if he buys \(\delta_i\) extra diamonds, his final count becomes \(f(i)=a_i+\delta_i\) and he will pay \(\delta_i\times b_i\) points. Your task is to help Q determine the minimum total number of points he must spend so that for every integer \(x\ge 2^k\) the condition above holds.

Note: For indices greater than \(n\), assume \(a_i=0\). The condition thereby applies non‐trivially only for those \(x\) for which some terms correspond to diamond types \(1\) through \(n\). One can show that it is optimal to set \(f(i)=a_i\) for all types \(i\) with \(i<2^k\) and then, for every \(i\ge 2^k\), to choose the smallest number \(f(i)\ge a_i\) satisfying

[ f(i)\equiv -\Bigl(f(\lfloor\tfrac{i}{2}\rfloor)+f(\lfloor\tfrac{i}{4}\rfloor)+\cdots+f(\lfloor\tfrac{i}{2^k}\rfloor)\Bigr)\pmod{m}. ]

This guarantees a minimum additional cost.

inputFormat

The input consists of three lines.

• The first line contains three integers \(n\), \(k\), and \(m\) (where \(1\le n\le 10^5\), \(1\le k\le \log_2(n)\), \(1\le m\le 10^9\)).
• The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(0\le a_i\le 10^9\)).
• The third line contains \(n\) integers \(b_1, b_2, \ldots, b_n\) (\(1\le b_i\le 10^9\)), where \(b_i\) is the cost (in points) per extra diamond of type \(i\).

You may assume that the input is such that a solution exists.

outputFormat

Output a single integer, the minimum number of points required for Q to satisfy the achievement condition.

sample

3 1 5
1 2 3
1 1 1

3