(Olympic Quốc Tế 1996)

Một nhà máy chạy một â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 mà 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 tại thời điểm 0.

Dữ liệu vào

Gồm các số nguyên dương ghi trên 5 dòng:

• Dòng thứ nhất ghi ~N~ số là số sản phẩm (1 <= ~N~ <= 1000)
• Dòg thứ hai ghi ~M_1~ là số lượng các máy kiểu A (1 <= ~M_1~ <= 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ư và thứ năm tương ứng ghi ~M_2~ là số lượng các máy kiểu ~B~ (1 <= ~M_2~ <= 30) và 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.

Kết quả

Ghi ra 2 dòng:

• 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

Ví dụ

INP

5
2
1 1
3 
3 1 4

OUT

3
5