Problem
Vers cần chuẩn bị báo cáo về lần xuất kích cuối cùng. Cô ấy đã soạn sẵn văn bản trong đầu, việc còn lại chỉ là viết nó ra. Báo cáo sẽ bao gồm hai phần: phần đầu tiên sẽ chứa n từ, iphần thứ ba bao gồm ai< /code> chữ cái, — thứ hai; m từ, jth trong số đó bao gồm các chữ cái bj. Ngôn ngữ Kriya không chứa bất kỳ dấu chấm câu nào. Vers phải viết báo cáo trên một cuộn giấy kẻ ô vuông, rộng w ô. Vì báo cáo bao gồm hai phần, cô ấy sẽ chia cuộn giấy thành hai phần trên toàn bộ chiều rộng bằng một đường thẳng đứng, sau đó cô ấy sẽ viết phần đầu tiên ở bên trái và bên phải — thứ hai.
Cả hai phần của báo cáo đều được viết theo cùng một cách, mỗi phần nằm trên một phần riêng của cuộn. Một chữ cái của từ chiếm chính xác một ô. Từ đầu tiên được viết ở dòng đầu tiên của cuộn, bắt đầu từ ô ngoài cùng bên trái của phần này của cuộn. Mỗi từ tiếp theo, nếu có thể, nên được viết trên cùng một dòng với từ trước đó và cách nhau đúng một ô trống.
Nếu không, nó được viết trên dòng tiếp theo, bắt đầu từ ô ngoài cùng bên trái. Nếu chiều rộng của một phần của cuộn nhỏ hơn chiều dài của một số từ nên được viết trong phần này, thì không thể viết phần này của báo cáo trên một phần của cuộn có chiều rộng như vậy.
Người ta đảm bảo rằng có thể vẽ một thanh dọc để có thể viết cả hai phần của báo cáo. Vers muốn vẽ một đường thẳng đứng sao cho độ dài của cuộn giấy đủ để viết báo cáo là nhỏ nhất. Hãy giúp cô ấy tìm độ dài tối thiểu đó.
Đầu vào:
- dòng đầu tiên chứa ba số nguyên w, n và m — chiều rộng cuộn, số từ trong phần đầu tiên và phần thứ hai của báo cáo (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));
- dòng tiếp theo cung cấp n số nguyên ai — độ dài của từ thứ i trong phần đầu tiên của báo cáo \(1 <= a_i <= 10^9\);
- dòng tiếp theo cung cấp số nguyên m bj — độ dài của từ thứ jtrong phần thứ hai của báo cáo \(1 <= b_j <= 10^9\).
Có thể đảm bảo rằng có thể vẽ một đường thẳng để có thể viết cả hai phần của báo cáo.
Input: trong một dòng in ra một số nguyên — chiều dài tối thiểu của cuộn, đủ để viết báo cáo.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
|
3 |
Lưu ý
Trong thử nghiệm mẫu, cuộn có thể được chia thành hai phần bằng cách kẻ một đường thẳng giữa cột ô thứ 7 và thứ 8, sau đó viết hai từ trên mỗi dòng trong cả hai phần của báo cáo.