For Valentine's Day, you have decided to get Evan a bouquet of flowers. There exist 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.
Constraints
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.
Instead, choose to get .
Comments
What is testcase 6??? Why do I have a wrong answer?
If you need help debugging your code, you can seek help on the DMOJ discord channel at https://discord.com/invite/EgJVpxz. The reason you have a wrong answer is because your code is wrong. I assure you the testcases are not wrong and nobody will tell you the testcases if they could.