Một nhà máy chạy một dây chuyền sản xuất. Có 2 nguyên công (2 giai đoạn độc lập nối tiếp nhau) cần phải thực hiện đối với mỗi một sản phẩm theo trình tự sau: Đầu tiên thực hiện nguyên công A, sau đó thực hiện nguyên công B. Có một số máy để thực hiện từng nguyên công (như vậy có hai loại máy: Máy thực hiện nguyên công A - máy kiểu A và máy thực hiện nguyên công B - Máy kiểu B). Dây chuyền sản xuất thực hiện như sau:

Máy kiểu A lấy sản phẩm từ băng chuyền vào, thực hiện nguyên công A và đặt sản phẩm vào băng chuyền trung gian. Máy kiểu B lấy sản phẩm từ băng chuyền trung gian, thực hiện nguyên công B và đặt sản phẩm vào băng chuyền ra. Mọi máy đều có thể làm việc song song và độc lập nhau, mỗi máy làm việc với thời gian xử lý cho trước. Thời gian xử lý là số đơn vị thời gian cần thiết để thực hiện nguyên công bao gồm cả thời gian lấy sản phẩm từ băng chuyền trước khi xử lý và thời gian đặt sản phẩm lên băng chuyền sau khi xử lý.

Câu a: Đưa ra thời điểm sớm nhất nguyên công A được hoàn thành đối với tất cả ~N~ sản phẩm với điều kiện là các sản phẩm này đã sẵn sàng trên băng chuyền vào tại thời điểm 0.

Câu b: Đưa ra một thời điểm sớm nhất mà cả hai nguyên công A và B được hoàn thành đối với tất cả ~N~ sản phẩm khi các sản phẩm này đã sẵn sàng trên băng chuyền vào thời điểm 0.

Yêu cầu: Hãy xác định thời điểm sớm nhất hoàn thành nguyên công A và thời điểm sớm nhất hoàn thành cả hai nguyên công A và B cho ~N~ sản phẩm.

Input

• Dòng thứ nhất ghi ~N~ là số sản phẩm (~1 \le N \le 1000~).
• Dòng thứ hai ghi ~M_1~ là số lượng các máy kiểu A (~1 \le M_1 \le 30~).
• Dòng thứ ba ghi ~M_1~ số nguyên là các thời gian xử lý của từng máy kiểu A.
• Dòng thứ tư ghi ~M_2~ là số lượng các máy kiểu B (~1 \le M_2 \le 30~).
• Dòng thứ năm ghi ~M_2~ số nguyên là các thời gian xử lý của từng máy kiểu B. Thời gian xử lý là một số nguyên nằm trong khoảng từ 1 đến 20.

Output

• Dòng đầu tiên chứa một số nguyên dương là lời giải của câu a.
• Dòng thứ hai là một số nguyên dương là lời giải của câu b.

Sample Input 1

5
2
1 1
3
3 1 4

Sample Output 1

3
5