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 \leq N, M, a_{i}, b_{i} \leq 300$

$0 \le m_i, p_i \le 1000$ $0 \leq m_{i}, p_{i} \leq 1000$

$a_i \ne b_i$ $a_{i} \neq 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

Copy

Sample Output 1

Copy

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

Copy

Sample Output 2

Copy

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.