Zhenya moves from the dormitory

题目链接：

http://acm.hust.edu.cn/vjudge/contest/126546#problem/D

Description

After moving from his parents’ place Zhenya has been living in the University dormitory for a month.
However, he got pretty tired of the curfew time and queues to the shower room so he took a fancy for
renting an apartment. It turned out not the easiest thing in the world to make a choice. One can live in
a one bedroom apartment or in a two bedroom apartment, alone or share it with a friend. Zhenya can
afford to rent an apartment of any type alone, but he can share only a two bedroom apartment. If two
people share an apartment, each pays half of the rent. Every apartment has its own advantages like part
of the town, floor, view from the windows, etc., which Zhenya is going to take into account to make a
decision.
Besides that, his friends, he’s ready to share an apartment with, also have certain advantages. For example,
Igor is a good cook, Dima is tidy, Kostya is a good cook and at the same time can explain how to solve
functional analysis problems. And do not forget that living alone has its own bright sides.
Zhenya has already prepared the list of suitable apartments and possible housemates. Zhenya has estimated
in units the advantages of each apartment and each friend and also the advantages of living alone. Besides,
he knows the maximum sum of money he and each of his friends is ready to pay for the apartment. Help
Zhenya to make a decision.

Input

The first line contains three integers: the maximum sum Zhenya is ready to pay monthly, the advantages of
living alone in a one bedroom apartment and the advantages of living alone in a two bedroom apartment.
The second line contains an integer