Blood Distribution

Time limit2sMemory limit512 MB

Summary

Given counts of eight blood types and matching patients, output the maximum number of patients who can each receive one compatible unit.

Level: Medium6 of 10
Topics: Greedy, Math, Implementation
Solved: No attempts yet

Problem

A cardiac centre stocks blood of the four ABO types O, A, B, and AB. Each unit of blood also carries an Rh factor that is either positive (+) or negative (−), so there are eight blood types in total.

Many patients each need exactly 1 unit of blood. Which blood a patient may receive is determined by the patient's own blood type.

ABO compatibility (which donor ABO type a patient may accept):

A type O patient may receive only type O blood.
A type A patient may receive type A or type O blood.
A type B patient may receive type B or type O blood.
A type AB patient may receive blood of any ABO type.

Rh compatibility:

An Rh-negative patient may receive Rh-negative blood only.
An Rh-positive patient may receive either Rh-positive or Rh-negative blood.

A patient can receive a unit of blood only if it is compatible in both ABO type and Rh factor. Distribute the available blood so that as many patients as possible each receive one unit, and output the maximum number of patients that can receive blood.

Input

The first line contains 8 integers: the number of units of blood of type O-negative, O-positive, A-negative, A-positive, B-negative, B-positive, AB-negative, and AB-positive, in that order.

The second line contains 8 integers: the number of patients whose blood type is O-negative, O-positive, A-negative, A-positive, B-negative, B-positive, AB-negative, and AB-positive, in that order.

Each of these integers is at least 0 and less than $10^7$ .

Output

Output a single integer: the maximum number of patients that can receive a unit of blood.

Explanation

For the sample input, one optimal way to serve 33 patients is:

2 type O− patients receive type O− blood
4 type O+ patients receive type O+ blood
3 type A− patients receive type A− blood
3 type A− patients receive type O− blood
1 type A+ patient receives type A+ blood
1 type A+ patient receives type O+ blood
2 type B− patients receive type B− blood
9 type B+ patients receive type B+ blood
5 type AB− patients receive type AB− blood
3 type AB+ patients receive type AB+ blood

Examples4

Example 1
Input
```
5 5 3 1 2 11 5 12
2 4 9 2 3 9 7 3
```
Expected output
```
33
```
Example 2
Input
```
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
```
Expected output
```
0
```

Example 3

Input

10 10 10 10 10 10 10 10
0 0 0 0 0 0 0 0

Expected output

Example 4
Input
```
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
```
Expected output
```
8
```