## Wesley's Anger Contest 4 Problem 6 - Hungry Squirrels

View as PDF

Points: 25 (partial)
Time limit: 3.0s
Java 5.0s
Memory limit: 256M

Author:
Problem type

The squirrel nation is preparing for quarantine! There are hungry squirrels that need to be fed. The exact amount of acorns that each squirrel consumes varies, but it is known that the squirrel will eat between and acorns during quarantine.

Before the quarantine begins, there are magical trees that will produce acorns that the squirrels can collect. The exact amount of acorns produced is also unknown due to seasonal fluctuations, but it is known that the tree will produce between and acorns before the quarantine begins. They will never produce an amount of acorns outside of this range.

Each squirrel will visit some of the trees and bring some of the acorns back to their home. The squirrel will collect at least and at most acorns from the tree. They will never collect an amount of acorns outside of this range. Obviously the total number of acorns taken from a tree cannot exceed the number of acorns that tree produces. In addition, squirrels do not like to waste food, so no acorns can be left on the trees before the quarantine begins, and no squirrel will bring home more acorns than they eat.

After the quarantine ends, Carson has been tasked with the job of collecting all the shells of the eaten acorns. Carson does not like working so he wants to determine both the minimum and maximum number of acorn shells that he will need to collect, over all possibilities where all squirrels survive the quarantine without wasting any food. The squirrel will survive the quarantine only if they eat between and acorns, and collect between and acorns from the tree. Food is wasted if there are acorns left on the trees or if there are uneaten acorns in any squirrel's home.

#### Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

for all
for all and
for all

for all
for all and
for all

Partial points can be earned based on the number of correct lines in your output. Please see the output specification section for more details.

#### Input Specification

The first line of input contains integers, and , representing the number of squirrels in the squirrel nation, and the number of magical trees producing acorns.

The next lines describe the number of acorns each squirrel will eat. The line contains integers, , , indicating that the squirrel will eat between and acorns during the quarantine.

The next lines describe the minimum number of acorns each squirrel will collect from each tree. Each line contains integers. The integer on the line is indicating that the squirrel will collect at least acorns from the tree.

The next lines describe the maximum number of acorns each squirrel will collect from each tree. Each line contains integers. The integer on the line is indicating that the squirrel will collect at most acorns from the tree.

The next lines describe the number of acorns each tree produces before the quarantine. The line contains integers, , , indicating that the tree will produce between and acorns before the quarantine.

#### Output Specification

This problem is graded with a custom checker. As usual, ensure that every line of output is terminated with a \n character and that there are no trailing spaces. This problem will NOT notify you if you have a presentation error.

If there is no way for all squirrels to survive the quarantine without wasting any food, output -1 and only -1 on a single line.

Otherwise, output two integers each on their own line. The first integer should be the minimum number of acorn shells that Carson will have to collect after the quarantine. The second integer should be the maximum number of acorn shells that Carson will have to collect after the quarantine.

For the test cases in the first subtask, you will receive points if all lines of output match the expected output correctly. Otherwise, you will receive points.

For the test cases in the second subtask, you will earn points only if you received points on the first subtask. If all lines of output match the expected output, you will receive additional points. If none of the lines of output match the expected output or if the number of lines of output is incorrect, you will receive additional points. Otherwise, you will receive additional points.

Your score for a subtask is equal to the minimum number of points earned for any case in that subtask.

#### Sample Input 1

3 2
0 1
0 4
0 0
0 0
0 0
0 0
2 0
1 3
0 1
0 3
0 2

#### Sample Output 1

0
4

#### Sample Explanation 1

There are squirrels and trees.

In this example, Carson will not have to collect any acorns if no squirrels eat any acorns, no matter how many acorns are produced.

Carson could have to collect acorns if the following occurs:

• tree produces acorns
• tree produces acorns
• squirrel collects acorn from tree , and eats acorn
• squirrel collects acorn from tree , acorns from tree , and eats acorns
• squirrel does not collect any acorns

#### Sample Input 2

2 2
3 4
0 1
0 0
0 0
1 1
1 1
1 2
1 2

#### Sample Output 2

-1

#### Sample Explanation 2

While squirrel can survive the quarantine without eating any acorns, there is no way for squirrel to eat at least acorns.

#### Sample Input 3

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

#### Sample Output 3

5
7

#### Sample Explanation 3

There are squirrels and trees.

Carson could only have to collect acorns if the following occurs:

• tree produces acorns, tree produces acorns, tree produces acorn
• squirrel collects acorns from tree , acorns from tree , and eats acorns
• squirrel collects acorn from tree , and eats acorn

Carson could have to collect acorns if the following occurs:

• tree produces acorns, tree produces acorns, tree produces acorns
• squirrel collects acorns from tree , acorns from tree , and eats acorns
• squirrel collects acorns from tree , and eats acorns

#### Sample Input 4

2 2
0 1
0 1
0 1
0 0
1 1
0 1
0 1
0 1

#### Sample Output 4

1
1

#### Sample Explanation 4

There are squirrels and trees.

Carson will always have to collect acorn over all possibilities where the squirrels survive the quarantine. Trees will always produce acorn, and squirrel will always eat that acorn. All other combinations lead to the squirrels not surviving the quarantine or food being wasted.