Sắn và các bạn trung tâm Kite được tham gia ngoại khoá ngày hội robot. Mỗi bạn được phép đem đến hội chợ một robot được lắp ghép từ các miếng logo. Các chú robot này khi di chuyển sẽ nhảy từng bước một, mỗi bước nhảy có độ dài cố định do các bạn làm ra robot đó chỉ định. Mỗi robot sẽ di chuyển trên một đường đua do ban tổ chức định sẵn. Đường đua độ dài L, các chú robot sẽ nhảy nếu bước nhảy không vượt ra ngoài đường đua. Chú robot nào gần đích nhất sẽ giành chiến thắng. Tuy nhiên độ dài đường đua L không được biết trước nên các bạn phải chủ động chọn bước nhảy cố định cho robot trước khi đem đến ngoại khoá.
Năm nay có N bạn tham dự thi, robot bạn thứ i nhảy a[i] (mm) mỗi bước. Sau khi trò chơi kết thúc ban tổ chức đo được khoảng cách còn lại từ vị trí cuối cùng của robot thứ i đến đích là p[i]. Sắn không chiến thắng trong trò chơi này nên muốn biết ban tổ chức đã chọn L là bao nhiêu. Bạn hãy lập trình giúp Sắn tìm L nhỏ nhất thoả mãn kết quả thu được.
Dữ liệu nhập:
- Dòng đầu tiên là số nguyên t – số trường hợp thử nghiệm (1 ≤ t ≤ 105)
- Mỗi trường hợp thử nghiệm gồm 3 dòng:
+ Dòng thứ nhất là số nguyên N - là số robot tham gia (1 ≤ n ≤ 12)
+ Dòng thứ hai là dãy số a[1], a[2], ..., a[n]. (0 ≤ a[i] < 40)
+ Dòng thứ ba là dãy số p[1], p[2], ...p[n]. (0 ≤ p[i] < a[i])
Kết quả:
- Mỗi trường hợp thử nghiệm in ra một số nguyên không âm nhỏ nhất (L) thoả mãn kết quả đề bài. Nếu không tìm được hãy in -1.
Ví dụinput23
5 7 11
4 6 3
4
2 3 5 7
1 2 3 1output69
113
Ràng buộc: 7đ full test.
- 60% test: Đáp án mỗi trường hợp không vượt quá 5000.
Giúp với ạ
