The Big Bad Wolf has just demolished the houses of the First and Second Little Pigs and devoured them, and he is now coming for the Third Little Pig! In less than a minute, the Third Little Pig will need to prepare fortifications with the maximum defensive value possible. To build these fortifications, there are three materials available, each with a unique defensive value. But in order to maximize his odds of survival, the Third Little Pig will need to micromanage every microsecond that can be spent gathering these materials.
- Straw is the easiest material to use; each bushel of straw can be gathered in a fixed amount of time.
- Sticks are more difficult to acquire; each bundle of sticks takes a variable amount of time to collect. The time cost of sticks fluctuates up and down in a repeating pattern and must be paid in sequential order.
- Bricks are the most difficult material to gather; making bricks is back-breaking labor, so the cost of bricks is always increasing. Like sticks, the increase in cost between consecutive bricks is a repeating pattern and must be paid in sequential order.
The defensive value of straw, sticks, and bricks is 1, 2, and 3 respectively. Resources are plentiful in Piglandia, so straw, sticks, and bricks will never run out.
With this knowledge, what is the maximum defensive value the Third Little Pig can attain in $$$t$$$ microseconds?
The first line of input contains $$$t$$$ ($$$0 \le t \le 10^7$$$), the number of microseconds the Third Little Pig has to prepare.
The second line contains $$$c$$$ ($$$1 \le c \le 10^7$$$), the fixed cost of straw.
The third line contains $$$n$$$ ($$$1 \le n \le 10^6$$$), the length of the repeating pattern that represents the time cost of sticks.
The fourth line contains $$$n$$$ integers $$$s_1, s_2, ..., s_n$$$ ($$$1 \le s_i \le 10^7$$$), a series of stick costs that repeats indefinitely.
The fifth line contains $$$b$$$ ($$$1 \le b \le 10^7$$$) and $$$m$$$ ($$$1 \le m \le 10^6$$$), the cost of the first brick and the length of the bricks' repeating pattern.
The sixth line contains $$$m$$$ integers $$$b_1, b_2, ..., b_m$$$ ($$$1 \le b_i \le 10^7$$$), a series of increases in cost between consecutive bricks that repeats indefinitely. For example, the second brick costs $$$b_1$$$ more than the first brick, and the third brick costs $$$b_2$$$ more than the second brick.
The output should be a single integer, the maximum defensive value that the Third Little Pig can attain.
12235 1 13 12
10
Straw will cost 2, 2, 2, ...
Sticks will cost 5, 1, 1, 5, 1, 1, ...
Bricks will cost 3, 5, 7, ...
The optimal choice of materials is 1 straw, 3 sticks, and 1 brick, giving a defensive value of $$$1 \cdot 1 + 3 \cdot 2 + 1 \cdot 3 = 10$$$.
