# acm cz

#### Czech ACM Student Chapter Czech Technical University in Prague

Charles University in Prague Technical University of Ostrava Slovak University of Technology Pavol Jozef Sˇaf´arik University in Koˇsice

University of Zˇilina Masaryk University Matej Bel University in Bansk´a Bystrica University of West Bohemia

### CTU Open Contest 2015

## Lunch Menu

lunch.c, lunch.cpp, Lunch.java, lunch.py

Willy is the youngest zookeper employed in the ZOO. His income is not exactly a billionaire’s one and he obviously has to plan his regular expenses carefully. Take for example his daily visit to the ZOO cantine. From the very beginning of his service in the ZOO, Willy decided that his daily lunch expense will not exceed a ﬁxed limit L. And while his budget is limited he still wants to have a complete lunch: A soup, a main dish, a dessert, and a beverage. Moreover, to keep himself amused, he wants to enjoy each day a diﬀerent menu, diﬀerent from all other menus he had eaten in the previous days. Now, he wonders how many days will it take until he is forced to eat a lunch which is an exact copy of another lunch he had already eaten before.

You are given Willy’s lunch price limit L and the prices of all soups, main dishes, desserts, and beverages in the cantine. Determine how many diﬀerent lunches can be assembled provided that two lunches are diﬀerent if they diﬀer in at least one of the four given parts.

### Input Specification

There are more test cases. Each case starts with a line containing ﬁve integers L, S, M, D, B N (1 ≤ L ≤ 108, 1 ≤ S, M, D, B ≤ 5 000) representing (in this order) the lunch price upper limit, the number of soups, the number of main dishes, the number of desserts and the number of beverages in the cantine. Each of the next four lines contains a list of prices. The ﬁrst line contains the soups price list, the second line contains the main dishes price list, the third line contains the desserts price list, and the fourth line contains the beverages price list. All items in all lists are positive integers not exceeding 108. There is one empty line after each test case. The input is terminated by a line with ﬁve zeros.

### Output Specification

For each test case print on a separate line the number of diﬀerent lunches which can be assembled from the cantine oﬀer and have price not exceeding L. Please note that the value of the solution might not ﬁt into 32-bit integer.

### Sample Input

11 3 1 1 1

4 5 6

3

2

1

10 4 5 4 2

### Output for Sample Input

2

48