Interrail passes are the fun and cheap way to see more of Europe, especially if you combine your train trip with Businesslike And Penny-saving Computation! In particular, you would like to find the cheapest way to pay for your planned travels. You plan to take the train on $$$n$$$ travel days, that are not necessarily consecutive. The individual fare is different for every day, and perhaps you can save money by buying some interrail passes.

There are $$$k$$$ different types of interrail passes with varying costs. Each type of interrail pass can be obtained multiple times. An interrail pass is active for a period of $$$p$$$ consecutive days, that starts on a day of your choice. The interrail pass covers the first $$$d$$$ travel days during this period, which do not have to be consecutive. Note that an active interrail pass cannot be "paused": a day of travel counts towards the day count of each active pass, even when you pay the individual fare that day.

As an example, consider the fourth sample input, visualized in the picture below. It is definitely cheaper to buy interrail passes than to pay $$$4$$$ individual fares. The cheapest solution is to buy two interrail passes of the first type, rather than one interrail pass of the second type.

Visualization of the types of interrail passes for the fourth sample input in a webshop. The first one can be activated for a period of $$$5$$$ days, and can be used for $$$3$$$ days within that period. The second one has a period of $$$30$$$ days, and can be used for $$$5$$$ days during that period.