Valentine's Day '19 J4 - Flowers

View as PDF

Points: 5
Time limit: 1.0s
Python 1.4s
Memory limit: 64M
Python 128M

Author:
Problem type

For Valentine's Day, you have decided to get Evan a bouquet of flowers. There exists types of flowers. Each type of flower first multiplies the beauty of the bouquet by and then increases its beauty by . Having two flowers of type does not apply the effect of flower twice. The initial beauty of the bouquet is and flowers can be added in any order.

Some flowers do not go together. There are such pairs where flowers and can not be in the same bouquet.

Because Evan will be receiving so many flowers, the size of your bouquet is limited to flowers.

You would like to stand out by maximizing the beauty of your flower bouquet.

Note: Python users are recommended to use PyPy.

Input Specification

The first line of input will contain integers and .

The next lines contain integers .

The next lines contain integers .

Output Specification

Print one number, the maximum beauty of your bouquet.

Sample Input 1

4 0
10 0
1 1
2 1
1 3

Sample Output 1

70

Explanation for Sample Output 1

Flower is chosen, giving a beauty value of . Then flower is chosen to yield . Finally, choose flower to get .

Sample Input 2

4 1
1 1
6 0
5 5
2 0
2 3

Sample Output 2

20

Explanation for Sample Output 2

While choosing flowers would give , flowers and can not be in the same bouquet.