TLE '16 Contest 6 (Mock CCC) J5 - Meal Plan
A first-year student in the University of Fireloo has been given 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 breakfast options, lunch options, and dinner options on campus, where the breakfast option has an integer cost , the lunch option has integer cost , and the dinner option has integer cost . 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?
The first line will contain , the student's current meal plan balance.
The second line will contain space-separated integers , , and , the number of options for each meal, in that order.
The third line will contain the space-separated integer cost for each of the breakfast options. You can assume all costs are distinct, and range from to .
The fourth line will contain the space-separated integer cost for each of the lunch options. You can assume all costs are distinct, and range from to .
The last line will contain the space-separated integer cost for each of the dinner options. You can assume all costs are distinct, and range from to .
Output two space separated integers: The number of different ways the student can use up his meal plan as much as possible, mod , 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.
750 2 3 3 100 200 200 400 300 325 300 400
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.