Valentine's Day '19 J4 - Flowers

View as PDF

Submit solution

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

Problem type

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

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

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

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

Note: Python users are recommended to use PyPy.


1 \le N, M, a_i, b_i \le 300

0 \le m_i, p_i \le 1000

a_i \ne b_i

Input Specification

The first line of input will contain integers N and M.

The next N lines contain integers m_i, p_i.

The next M lines contain integers a_i, b_i.

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


Explanation for Sample Output 1

Flower 4 is chosen, giving a beauty value of 3. Then flower 3 is chosen to yield 3 \times 2 + 1 = 7. Finally, choose flower 1 to get 7 \times 10 = 70.

Sample Input 2

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

Sample Output 2


Explanation for Sample Output 2

While choosing flowers 3, 4, 2 would give 60, flowers 2 and 3 can not be in the same bouquet.

Instead, choose 1, 3, 4 to get 20.


  • 0
    TingHoMarcus  commented on Feb. 20, 2019, 12:05 p.m. edited

    What is testcase 6??? Why do I have a wrong answer?

    • -2
      HyperNeutrino  commented on Feb. 24, 2019, 3:01 a.m. edit 12

      If you need help debugging your code, you can seek help on the DMOJ discord channel at 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.