Maximum Beauty Potion

You are given n flowers, each with a beauty value and a magic value. Your task is to select exactly k consecutive flowers such that the product of the magic values of the chosen flowers does not exceed a given threshold m, i.e. \(\prod_{i=1}^{k} magic_i \le m\). Among all valid selections, you need to maximize the sum of the beauty values.

If no consecutive block of k flowers meets the condition, output impossible.

Note: The condition can be written in LaTeX as \(\prod_{i=1}^{k} magic_i \le m\).

inputFormat

The input is read from stdin and consists of three lines:

• The first line contains three space-separated integers: n (the number of flowers), k (the number of consecutive flowers to pick), and m (the magic threshold).
• The second line contains n space-separated integers representing the beauty values of the flowers.
• The third line contains n space-separated integers representing the magic values of the flowers.

It is guaranteed that k ≤ n.

outputFormat

Output the maximum total beauty value of any valid sequence of k consecutive flowers on stdout. If no valid block exists (i.e. for every block, \(\prod_{i=1}^{k} magic_i\) exceeds m), output impossible.

7 3 1000
5 1 9 8 3 2 7
2 4 1 2 5 3 4

20