WC '18 Finals S1 - Behind the Scenes

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type
Woburn Challenge 2018-19 Finals Round - Senior Division

The cows and monkeys of Scarberia, their long-standing conflicts well behind them at last, have banded together to produce a historical drama documenting their past battles. With the Head Monkey as writer and producer, and the director's chair occupied by the cows' leader, Bo Vine, this will be a collaborative masterpiece to remember!

Today, a full day of filming is set to take place at the monkeys' and cows' joint studios. The studios feature three sound stages, numbered from 1 to 3, and there are initially E_i (0 \le E_i \le 1\,000) pieces of filmmaking equipment on stage i.

A sequence of N (1 \le N \le 1\,000) shots will be filmed, one after another, with the i-th one taking place on stage S_i (1 \le S_i \le 3). Whenever a shot is filmed on a certain stage, there must be no equipment present on that stage at the time. Right before each shot, Bo Vine may choose 0 or more pieces of equipment to be moved. Each such piece will be moved from its current stage to a different stage of Bo's choice, at the cost of tipping a stagehand $1, and will remain there until potentially moved again later.

What's the minimum total cost of stagehand tips which Bo Vine will need to dispense such that each of the N shots will have no equipment present on its stage at filming time?

Input Specification

The first line of input consists of three space-separated integers, E_1, E_2, and E_3.
The next line consists of a single integer, N.
N lines follow, the i-th of which consists of a single integer, S_i, for i = 1 \dots N.

Output Specification

Output a single integer, the minimum total cost of stagehand tips required, in dollars.

Sample Input

6 3 4
5
3
2
2
1
2

Sample Output

17

Sample Explanation

One possible optimal strategy for Bo Vine is as follows:

  • Before the 1st shot, move all 4 pieces of equipment from stage 3 to stage 2.
  • Before the 2nd shot, move all 6 pieces of equipment from stage 1 to stage 3, and all 7 pieces of equipment from stage 2 to stage 3.

This requires $4 + $6 + $7 = $17 in stagehand tips.


Comments

There are no comments at the moment.