Advanced Programming, Jan-Apr 2011
                          Assignment 6
                   Due Friday, 15 April, 2011

The owners of a small petrol pump in the Himalayas are faced with
the following situation.  They have an underground tank in which
they can store petrol; the tank can hold upto L litres at one
time.  Because it is a mountainous region, the oil companies
charge extra to send petrol tankers to deliver petrol, so they
want to order relatively rarely.  For each order they need to pay
a fixed price P for delivery in addition to the cost of the
petrol ordered.  However, there is a maintenance cost associated
with the storage tank: it costs C per day to store a litre of
petrol, so ordering too much ahead increases the storage cost.

They are planning to close for a week in the winter, and they
want their tank to be empty by the time they close.  Luckily,
based on years of experience, they have accurate projections of
how much petrol they will need each day until they close.  Assume
that there are N days left until they close, and they need l_i
litres of petrol for each of the days i = 1,2,...,N.  Assume that
they start with an empty tank, so they must order petrol on day 1
if there is a requirement to be filled on day 1.

For instance, suppose that the tank can hold 18 litres, the
delivery cost is 15 and the storage cost per litre per day is 2.
There are 5 days to go and the projected daily requirement is

      ---------------------------------------
     | Day (i)           | 1 | 2 | 3 | 4 | 5 |
      -------------------+---+---+---+---+---
     | Requirement (l_i) | 0 | 7 | 2 | 1 | 8 |
      ---------------------------------------

If the owners take a single delivery of 18 litres on day 2, they
pay a delivery cost of 15 but the storage cost is 56, so the
total cost is 71.  Instead, they can take delivery of 10 litres
on day 2 and 8 litres on day 5.  For this, the delivery cost is
30, but the storage cost is only 8, so the total cost is only 38.
You can check that there is no better option.

Write a Python program to decide on which days they should place
orders, and how much to order, so as to minimize their cost.  You
should name your file "assignment6.py".

INPUT FORMAT

The first line of input has four integers, L, P, C and N, whose
interpretations are as stated in the problem.  The second line of
input has N non-negative integers: the projected demand l_i for
days i = 1,2,...,N.

OUTPUT FORMAT

The first line of output should consist of two integers TC and
DN, where TC is the total cost of an optimal solution and DN is
the number of days on which petrol should be delivered.  This
should be followed by DN lines of output, describing the days on
which petrol is ordered.  Each of these DN lines should contains
two integers D and O where D is the day number and O is the
amount ordered.

LIMITS

You can assume that 1 <= N <= 5000.

SAMPLE INPUT

18 15 2 5
0 7 2 1 8

SAMPLE OUTPUT

38 2
2 10
5 8

======================================================================