Escape from the Dark Forest

After being detected and attacked in the dark forest, the ccj creatures decide to flee their home. Their journey is along a straight line of planets. We label the home as planet 1, which has an infinite supply of creatures. Every other planet has a limit on the number of creatures it can accept, which is given as an interval \([b, a]\). From any planet, the creatures can transfer to one of the next \(p\) consecutive planets. However, arriving at any planet requires spending energy. The energy cost is a polynomial function in the number of creatures landing on that planet. In particular, if \(x\) creatures land on a planet, the energy cost incurred is

[ f(x) = c_{0} + c_{1}x + c_{2}x^2 + \cdots + c_{d}x^d ]

where (d) is the degree of the polynomial and (c_0, c_1, \ldots, c_d) are given coefficients.

Initially, at planet 1, there are infinitely many creatures, so the first jump can use any number in the range \([b,a]\). After each jump, the number of creatures available is exactly the number that landed, and the same limit applies for subsequent transfers (i.e. you may only send an amount in the range \([b, \min(a, x)]\); note that choosing \(b\) is always feasible). Thus, one valid strategy is to always send exactly \(b\) creatures at each jump. Since each jump costs \(f(b)\), and a jump can cover at most \(p\) planets ahead, the minimum number of jumps needed to reach a habitable planet (planet \(n\)) is

[ \text{jumps} = \left\lceil \frac{n-1}{p} \right\rceil ]

Thus, the minimum total energy consumption is

[ \text{Total Energy} = \left\lceil \frac{n-1}{p} \right\rceil \times f(b). ]

Your task is to compute this minimum total energy consumption given the parameters of the journey and the polynomial coefficients.

inputFormat

The input consists of two lines:

• The first line contains five space-separated integers: n p b a d, where n is the index of the habitable planet (\(n \ge 2\)), \(p\) is the maximum jump range, and \(b\) and \(a\) (with \(b \le a\)) are the lower and upper limits on the number of creatures that can be accepted by a planet, and \(d\) is the degree of the energy cost polynomial.
• The second line contains \(d+1\) space-separated integers representing the coefficients \(c_0, c_1, \ldots, c_d\) of the polynomial f(x) = c0 + c1*x + c2*x^2 + ... + cd*x^d.

You may assume that all numbers are integers and that a solution exists.

outputFormat

Output a single integer representing the minimum total energy consumption required for at least one creature to reach the habitable planet.

sample

10 3 2 5 2
1 2 1

27