URI Online Judge | 1210

Optimal Production of Great Vodka

By Marcio T. I. Oshiro, USP  Brazil

Timelimit: 1

The production of vodka from the city of St. Petersburg is famous around the world. The legend is that the vodka produced is distributed directly into the home of some of the most senior officers of the company through the water supply system. That is, just open the tap and pours ice cold vodka (after all the pipes are running at a negative temperature most of the year) of the barrel. This causes many security problems, after all people dig the streets looking for the alleged pipes vodka leaving the company.

This is not the only problem faced in the production of vodka in town. To ensure the quality standards required of the drink, it is produced in only one still having a life well-defined M years. Maintaining varies depending on the age of the equipment. The maintenance cost is Ci, where i is the age of the distiller, and must be paid every year, even for new distillers. These stills have a price when purchased new P (age 0) and distillers used in Russian factories are played by distilleries worldwide, where they are still used for many years, and museums. The selling price of a distiller with age i is Vi.

Note that a distiller with agie M can't longer be used and must be sold. Your task in this problem is deciding which moments in the company will replace the distiller to minimize the cost of production at the end of N years (from year 1). Consider that the exchange of stills can be done only at the beginning of the year.

Input

The input contains many test cases and ends with EOF. The first line of each test case contains 4 integers, N (1 ≤ N ≤ 2000), I (1 ≤ lM), M (1 ≤ M ≤ 2000) and P (1 ≤ P ≤ 1000) representing, respectively, the period of production, the initial distiller age, the maximun destiler age and the price of a new distiller.

The second line of each test case contains M integers, separated by spaces, corresponding to the maintenance cost Ci (1 ≤ Ci ≤ 1000), for i = 0,1,2, ... M - 1. The next and last line contains M integers, separated by spaces, corresponding to the sell value Vi (1 ≤ ViP), for i = 1,2, ..., M.

Output

For each test case print two lines. At first, print the minimum cost for the given period. In the second, an increasing sequence of integers, separated by spaces, indicating the years in which the machines are exchanged. If the machine is never exchanged, then print only a 0. If there is more than one possible sequence, choose one in which machines are exchanged as soon as possible and whenever possible (eg, between the sequences "1 4 7" and "1 2 8 10 14" second choice).

Input Sample Output Sample

4 2 6 100
30 50 65 80 100 120
60 50 40 30 20 10
5 5 6 200
1 100 100 100 100 200
50 100 100 100 100 100

260
1 3
501
1