Electronics Shop

Source: HackerRank

Version: Phuoc Hung OJ Extended

Problem

Given budget $B$, keyboard prices $k_0,\ldots,k_{n-1}$, and USB-drive prices $d_0,\ldots,d_{m-1}$, buy exactly one item from each list.

Find

If no valid pair exists, print $-1$.

Input

The first line contains $B$, $n$, and $m$. The next two lines contain keyboard and USB-drive prices.

Output

Print the maximum affordable total, or $-1$ if no pair can be bought.

Subtask

Subtask 1 (20 points): $1\le n,m\le10$, $1\le B,k_i,d_j\le10^6$.

Subtask 2 (30 points): $1\le n,m\le100$, $1\le B,k_i,d_j\le10^6$.

Subtask 3 (50 points): $1\le n,m<1000$, $1\le B,k_i,d_j\le10^6$.

Example

Input

10 2 3
3 1
5 2 8

Output

9

Explanation

The result follows directly from the mathematical definition above.