Monkey Mischief

The zoo has recently acquired a large, open garden where animals roam freely – just as they would in their natural habitats – and entertain the visitors with their mischief. The most popular animals in the garden are the monkeys. They swing, jump, and perform amusing antics that delight the audience.

There are two types of monkeys involved. The first type, consisting of n monkeys numbered from 1 to n, climbs trees to pick coconuts. The k-th monkey of this type takes \(A_k\) seconds to find a good perch on a tree and pick its first coconut, and then produces one additional coconut every \(B_k\) seconds.

The second type, consisting of m monkeys numbered from 1 to m, opens the coconuts. The k-th monkey of the second type takes \(C_k\) seconds to find the proper tool to open a coconut and opens its first coconut, and then opens one more coconut every \(D_k\) seconds.

Unfortunately, these two types of monkeys cannot be in the garden at the same time. The zoo administrator drives away the first type immediately after they have picked all the coconuts, and later, drives away the second type immediately after they have opened all the coconuts – as any delay might trigger fights among them.

The administrator arrives at the garden exactly at the moment when all the coconuts have been picked and leaves exactly when all the coconuts have been opened. (The time for the monkeys to enter or leave is negligibly small.)

Tomislav is especially fond of the second type of monkey, but he never gets to see them because of the tight schedule. Given the total time \(T_{total}\) that the monkeys spend in the garden and the parameters of both types of monkeys, help Tomislav determine at what time the second type of monkeys arrives (i.e. the time when the first type is dismissed).

Note: The number of coconuts \(X\) is not known in advance. It satisfies \(X = f(t_1)\) where \[ f(t_1) = \sum_{k=1}^{n} \begin{cases} 0, & t_1 < A_k,\\ 1 + \left\lfloor \frac{t_1 - A_k}{B_k} \right\rfloor, & t_1 \ge A_k, \end{cases} \] and the time \(t_2\) required for the second type satisfies \[ g(t_2) = \sum_{k=1}^{m} \begin{cases} 0, & t_2 < C_k,\\ 1 + \left\lfloor \frac{t_2 - C_k}{D_k} \right\rfloor, & t_2 \ge C_k. \end{cases} \] The administrator’s schedule forces \[ t_1 + t_2 = T_{total}, \] and your task is to compute \(t_1\), the time at which the second type of monkeys arrives.

inputFormat

The first line contains three integers \(T_{total}\), \(n\), and \(m\) representing the total time (in seconds) the monkeys spend in the garden, the number of first-type monkeys, and the number of second-type monkeys respectively.

The second line contains \(n\) integers: \(A_1, A_2, \dots, A_n\).

The third line contains \(n\) integers: \(B_1, B_2, \dots, B_n\).

The fourth line contains \(m\) integers: \(C_1, C_2, \dots, C_m\).

The fifth line contains \(m\) integers: \(D_1, D_2, \dots, D_m\).

outputFormat

Output a single integer denoting \(t_1\), the time (in seconds) when the second type of monkeys arrive (i.e. when the first type has finished picking all the coconuts).

sample

6 1 1
1
1
1
1

3