Problem 2: Renting
Equipment, *(K Narayan Kumar, CMI)*

The Chennai Mathematical Institute (CMI) organises a number of seminars throughout the year. These seminars require audio-visual equipment like projectors, microphones, speakers and so on. CMI rents this equipment from S.W.Indler and Co.

The cost of renting such equipment consists of three parts: a initial flat charge (to cover the transport and setting up of the equipment), a daily rental and finally a winding down charge (for dismantling and transporting the equipment back).

CMI is a very organised institute and the office secretary knows the
schedule of seminars for the next *N* days. He would
like to place orders for the equipment from S.W.Indler and Co. so
that the total cost to the institute is minimized.

Notice that it might make sense to keep rented equipment even on days without seminars as this expenditure might be less that the cost incurred in returning and then re-renting the equipment. Suppose seminars are to be held on days 1, 3, 5 and 12. If the initial cost is 500, the daily rental is 200 and the winding up cost is 250, then it makes sense to rent the equipment on the 1st day, return it on the 5th day, rent it again on the 12th day and return it on the same day. The total cost works out to (500+200*5+250) + (500+200+250) = 2700. You can verify that this is the minimum possible cost.

Your task is to help the secretary determine the minimum possible cost for any schedule of seminars.

Input format

The first line of the input contains 3 integers *I*,
*R* and *W* denoting the initial charge, the daily
rental and the winding up charge, respectively. The second line
contains a single integer *N* indicating the number of
days for which the secretary knows the schedule. The third line
has *N* entries giving information about the schedule of
lectures. Each entry on this line is either 0 or 1. If the
*i*th entry on the line is 0 then there are no seminars
scheduled for the *i*th day. If the *i*th entry on
the line is 1 then there is a seminar scheduled for the
*i*th day.

Output format

A single line containing the minimum cost of hiring the equipment.

Test data

You may assume that *N* ≤ 100000. You may further
assume that in 50% of the inputs *N* ≤ 5000.

Example

We now illustrate the input and output formats using the above example.

Sample input

500 200 250 12 1 0 1 0 1 0 0 0 0 0 0 1

Sample output

2700

Copyright (c) IARCS 2003-2018; Last Updated: 17 Jul 2005