Cheapest pass plan: hints, no solution

A shop owner knows the days on which they will visit a wholesale market, given as a strictly increasing list visitDays. Passes come in several types: a pass of type t costs prices[t] and, when bought on any day d, covers every day from d through d + durations[t] - 1. You may buy any number of passes of any type on any day, including days without a visit, and passes may overlap. Return the lowest total cost so that every visit day is covered. With no visit days the cost is 0.

Examples

Input

visitDays = [2, 3, 5, 9, 10, 11, 30], durations = [1, 4, 10], prices = [3, 8, 15]

Output

18

Note

One 10-day pass from day 2 covers days 2 to 11 for 15, and a one-day pass covers day 30 for 3.

Input

visitDays = [1, 2, 3], durations = [1], prices = [4]

Output

12

Note

Only one-day passes exist, so each visit needs its own.

Input

visitDays = [], durations = [7], prices = [10]

Output

0

Constraints

• 0 <= visitDays.length <= 100000, strictly increasing, 1 <= visitDays[i] <= 1000000
• 1 <= durations.length <= 6, and prices has the same length
• 1 <= durations[t] <= 1000000, 1 <= prices[t] <= 100000

Hint 1: a nudge

Look at the earliest visit day you have not covered yet. What are the possible passes you could buy for it, and what remains after each choice?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing