## GlobeX Cup '19 J2 - Winnie Waifu Wars

View as PDF

Points: 3 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Winnie is playing the latest hot mobile game, AliensXBattle 2. In this game, Winnie has aliens on the field. Each alien starts at level , but can be upgraded by using coins and alien drinks. The maximum level of each alien is . Each alien has a power level. The power level of each alien changes based on level. Help Winnie determine the maximum sum of power levels she can achieve.

#### Input Specification

The first line of input contains two integers and . is the amount of coins Winnie has, and is the amount of alien drinks Winnie has.

The second line of input contains two integers and . is the amount of coins to level up an alien, and is the amount of alien drinks needed to level up an alien.

Each of the next lines of input contains integers, . represents the power level of the alien at level . It is not guaranteed that an alien will increase their power level as they level up.

#### Output Specification

Output the maximum power level Winnie can achieve by upgrading her aliens.

#### Constraints

(Hint: What do these constraints tell you about the problem?)

#### Sample Input 1

1 1
1 1
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

#### Sample Output 1

7