Indian National Olympiad in Informatics

Related:

Online Programming Contest, 9-10 July 2005

IARCS home > OLYMPIAD

Basic Division

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 ith entry on the line is 0 then there are no seminars scheduled for the ith day. If the ith entry on the line is 1 then there is a seminar scheduled for the ith 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