H. Chicken Farm
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is playing a popular block game, and has $$$n$$$ days to collect as many eggs as she can. Alice initially has 1 chicken that lays an egg every day and needs 1 night of sleep. Every day, she can throw as many eggs as she wants to hatch more chickens.

Alice knows the seed of her game generated world, which gives her some additional information. In fact, she knows how many eggs she must throw to hatch another chicken, and how many nights of sleep each chicken needs before laying an egg. In fact, these values follow a predictable pattern. Help Alice find the maximum amount of eggs that she can have in $$$n$$$ days.

Note that throwing an egg requires that you have at least 1 egg, and the act of throwing an egg decreases the amount of eggs you have by 1.

Input

The first line of input will contain the integers $$$n$$$ ($$$1 \leq n \leq 60$$$) and $$$m$$$ ($$$1 \leq m \leq 10^4$$$), the number of days Alice has to collect eggs and the length of the arrays containing each chicken's information.

The second line of input will contain $$$m$$$ integers $$$c_1, c_2, ..., c_m$$$ ($$$1 \leq c_i \leq n$$$), where $$$c_i$$$ represents the hatching cost of chickens $$$i, i + m, i + 2m, ...$$$.

The third line of input will contain $$$m$$$ integers $$$r_1, r_2, ..., r_m$$$ ($$$1 \leq r_i \leq n$$$), where $$$r_i$$$ represents the number of nights of sleep needed by chickens $$$i, i + m, i + 2m...$$$ beforing laying an egg.

Note that Alice may hatch more than $$$m$$$ chickens. The pattern repeats once the $$$m-th$$$ chicken is hatched, and the $$$m+1th$$$ chicken has the same hatching cost and sleep requirement as the first hatched chicken.

Examples
Input
8 3
1 2 1
1 2 3
Output
23
Input
7 1
1
1
Output
64
Input
10 2
1 2
2 1
Output
37