Problem G
Kayaking Trip
The kayaks are of different types and have different amounts of packing, so some are more easily paddled than others. This is captured by a speed factor $c$ that you have already figured out for each kayak. The final speed $v$ of a kayak, however, is also determined by the strengths $s_1$ and $s_2$ of the two people in the kayak, by the relation $v=c(s_1+s_2)$. In your group you have some beginners with a kayaking strength of $s_ b$, a number of normal participants with strength $s_ n$ and some quite experienced strong kayakers with strength $s_ e$.
Input
The first line of input contains three non-negative integers $b$, $n$, and $e$, denoting the number of beginners, normal participants, and experienced kayakers, respectively. The total number of participants, $b+n+e$, will be even, at least $2$, and no more than $100\, 000$. This is followed by a line with three integers $s_ b$, $s_ n$, and $s_ e$, giving the strengths of the corresponding participants ($1 \leq s_ b < s_ n < s_ e \leq 1\, 000$). The third and final line contains $m = \frac{b+n+e}{2}$ integers $c_1, \ldots , c_ m$ ($1 \leq c_ i \leq 100\, 000$ for each $i$), each giving the speed factor of one kayak.
Output
Output a single integer, the maximum speed that the slowest kayak can get by distributing the participants two in each kayak.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 0 40 60 90 18 20 |
1600 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 0 7 5 10 500 1 1 1 1 1 1 1 |
505 |
