Farmer

A farmer has several gardens and several furrows. Each garden is a closed cycle, while each furrow is a straight line whose two ends are not connected. Cypress trees are planted along each garden boundary and each furrow. Between every adjacent pair of cypress trees on the same garden or furrow, there is exactly one olive tree.

The son may choose one or more contiguous segments on garden boundaries or furrows. If the total number of chosen cypress trees is at most Q, he receives those cypress trees and every olive tree between two consecutive chosen cypress trees inside each chosen segment.

Because a garden is a cycle, choosing every cypress tree in one garden also gives the olive tree between the last and first cypress trees. Therefore, choosing an entire garden with n cypress trees gives n olive trees. In contrast, choosing x consecutive cypress trees from a furrow or from only part of a garden gives x-1 olive trees.

Given the numbers of cypress trees in all gardens and furrows, compute the maximum number of olive trees the son can receive.

The first line contains Q, the maximum number of cypress trees the son may choose, M, the number of gardens, and K, the number of furrows. The second line contains M integers, the numbers of cypress trees in the gardens. The third line contains K integers, the numbers of cypress trees in the furrows.

0 ≤ Q ≤ 150,000 and 0 ≤ M, K ≤ 2,000. Each garden or furrow contains between 2 and 150 cypress trees, inclusive. The total number of cypress trees in all gardens and furrows is at least Q.

Output the maximum number of olive trees the son can receive.