For Valentine's Day, you have decided to get Evan a bouquet of flowers. There exists 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

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

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 slack channel at https://dmoj.slack.com. 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.