Valentine's Day '19 J4 - Flowers - DMOJ: Modern Online Judge

Valentine's Day '19 J4 - Flowers

Points: 5

Time limit: 1.0s

Python 1.4s

Memory limit: 64M

Python 128M

Author:

crackersamdjam

Problem type

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

Some flowers do not go together. There are $M$ ~M~ such pairs where flowers $a_i$ ~a_i~ and $b_i$ ~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$ ~3~ flowers.

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

Note: Python users are recommended to use PyPy.

Constraints

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

$0 \le m_i, p_i \le 1000$ ~0 \le m_i, p_i \le 1000~

$a_i \ne b_i$ ~a_i \ne b_i~

Input Specification

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

The next $N$ ~N~ lines contain integers $m_i$ ~m_i~, $p_i$ ~p_i~.

The next $M$ ~M~ lines contain integers $a_i$ ~a_i~, $b_i$ ~b_i~.

Output Specification

Print one number, the maximum beauty of your bouquet.

Sample Input 1

Sample Output 1

Explanation for Sample Output 1

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

Sample Input 2

Sample Output 2

Explanation for Sample Output 2

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

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

Comments

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 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.