Electronics Shop

Nguồn: HackerRank

Phiên bản: Phước Hưng OJ Extended

Đề bài

Bạn có ngân sách $B$, $n$ mẫu bàn phím với giá

$$k_0,k_1,\ldots,k_{n-1},$$

và $m$ mẫu USB với giá

$$d_0,d_1,\ldots,d_{m-1}.$$

Phải mua đúng một bàn phím và đúng một USB. Với cặp $(i,j)$, tổng chi phí là

$$c_{i,j}=k_i+d_j.$$

Trong các cặp thỏa

$$c_{i,j}\le B,$$

hãy tìm tổng chi phí lớn nhất

$$M=\max\{k_i+d_j\mid 0\le i<n,\ 0\le j<m,\ k_i+d_j\le B\}.$$

Nếu không tồn tại cặp hợp lệ, in $-1$.

Input

Dòng đầu chứa $B$, $n$, $m$. Dòng thứ hai chứa $n$ giá bàn phím. Dòng thứ ba chứa $m$ giá USB.

Output

In tổng tiền lớn nhất không vượt ngân sách, hoặc $-1$ nếu không thể mua cả hai món.

Subtask

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

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

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

Ví dụ

Input

10 2 3
3 1
5 2 8

Output

9

Giải thích

Các cặp hợp lệ có tổng $8,5,6,3,9$; lớn nhất là $9=1+8$.