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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

For Valentine's Day, you have decided to get Evan a bouquet of flowers. There exists 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 \leq N, M, a_i, b_i \leq 300

0 \leq m_i, p_i \leq 1000

a_i \neq 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



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



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, 7:05 a.m. edited

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

    • -2
      HyperNeutrino  commented on Feb. 23, 2019, 10:01 p.m. edit 11

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