TLE '16 Contest 6 (Mock CCC) J5 - Meal Plan

Points: 10 (partial)

Time limit: 0.5s

Memory limit: 256M

Author:

Problem type

A first-year student in the University of Fireloo has been given $N$ ~N~ dollars to pay only for food on campus, also known as his meal plan. The problem is, if he doesn't use up all of his meal plan money, the remaining balance will be lost. So the student wants to use up his meal plan as much as possible.

Every day, the University of Fireloo offers the same $B$ ~B~ breakfast options, $L$ ~L~ lunch options, and $D$ ~D~ dinner options on campus, where the $i^\text{th}$ ~i^\text{th}~ breakfast option has an integer cost $b_i$ ~b_i~, the $i^\text{th}$ ~i^\text{th}~ lunch option has integer cost $l_i$ ~l_i~, and the $i^\text{th}$ ~i^\text{th}~ dinner option has integer cost $d_i$ ~d_i~. The student can use his meal plan only for these options. Each day, the student can order a maximum of one breakfast option, one lunch option, and one dinner option. Also, before ordering lunch, he must have had breakfast on the same day, and before ordering dinner, he must have had lunch on the same day. The student gets hungry very easily, so he must have eaten all three meals before considering breakfast for the next day.

Starting on a new day with no meals eaten yet, what is the lowest possible remaining balance the student can have in his meal plan following these rules? Moreover, how many different ways can he remain with such balance?

Input Specification

The first line will contain $N$ ~N~ $(1 \le N \le 2000)$ ~(1 \le N \le 2000)~, the student's current meal plan balance.

The second line will contain space-separated integers $B$ ~B~, $L$ ~L~, and $D$ ~D~ $(1 \le B, L, D \le 50)$ ~(1 \le B, L, D \le 50)~, the number of options for each meal, in that order.

The third line will contain the space-separated integer cost for each of the $B$ ~B~ breakfast options. You can assume all costs are distinct, and range from $1$ ~1~ to $2000$ ~2000~.

The fourth line will contain the space-separated integer cost for each of the $L$ ~L~ lunch options. You can assume all costs are distinct, and range from $1$ ~1~ to $2000$ ~2000~.

The last line will contain the space-separated integer cost for each of the $D$ ~D~ dinner options. You can assume all costs are distinct, and range from $1$ ~1~ to $2000$ ~2000~.

Output Specification

Output two space separated integers: The number of different ways the student can use up his meal plan as much as possible, mod $1\,000\,000\,007$ ~1\,000\,000\,007~, followed by the minimum remaining meal plan balance he could end with. If the student cannot buy anything at all using his meal plan, then there are 0 ways he can use the most of it.

Sample Input

750
2 3 3
100 200
200 400 300
325 300 400

Sample Output

3 25

Explanation for Sample Output

The student can either:

pay 100 for breakfast, 300 for lunch, and 325 for dinner;
pay 200 for breakfast, 200 for lunch, and 325 for dinner;
pay 100 for breakfast, 200 for lunch, 325 for dinner, and 100 for the next breakfast.

Comments

-1

marshmelllo commented on March 21, 2017, 9:03 p.m.

What does it want us to print if he cannot pay for breakfast, lunch, and dinner? Just 0?

4

ChaSiu commented on March 22, 2017, 9:21 p.m. ← edited →

The output should always be two numbers: the number of different ways the student can use up the most of his meal plan, and the remaining balance, no matter the case.

25

P234rex commented on Feb. 22, 2017, 1:35 a.m.

Waterloo, Earthloo, Fireloo, Airloo. Long ago, the four Loos lived together in harmony. Then everything changed when Fireloo attacked. Only the Avaloo, master of all four elemeloos, could stop them. But when the world needed him most, he vanished.