Xưởng gốm hai công đoạn

Một nhà máy gốm có hai phân xưởng: xưởng nặn và xưởng vẽ. Mỗi sản phẩm phải được nặn ở xưởng nặn, sau đó vẽ ở xưởng vẽ. Trong một ngày, toàn bộ sản phẩm đã nặn chỉ được chuyển sang xưởng vẽ đúng một lần duy nhất (thời gian chuyển bằng \(0\)), tức là xưởng vẽ chỉ bắt đầu sau khi xưởng nặn đã ngừng hẳn.

Xưởng nặn có \(N\) thợ, thợ thứ \(i\) nặn xong một sản phẩm trong \(a_i\) đơn vị thời gian. Xưởng vẽ có \(M\) thợ, thợ thứ \(j\) vẽ xong một sản phẩm trong \(b_j\) đơn vị thời gian. Mỗi thợ làm việc độc lập, làm lần lượt từng sản phẩm. Ngày làm việc dài \(T\) đơn vị thời gian; đầu ngày không có sản phẩm nào và cuối ngày mọi sản phẩm được tính phải đã nặn xong và vẽ xong.

Hãy tính số sản phẩm nhiều nhất có thể hoàn thành trong ngày.

Input

• Dòng thứ nhất chứa số nguyên \(T\).
• Dòng thứ hai chứa số nguyên \(N\).
• Dòng thứ ba chứa \(N\) số nguyên \(a_1, \dots, a_N\).
• Dòng thứ tư chứa số nguyên \(M\).
• Dòng thứ năm chứa \(M\) số nguyên \(b_1, \dots, b_M\).

Output

In ra một số nguyên là số sản phẩm tối đa.

Constraints

• \(1 \le T \le 10^9\).
• \(1 \le N, M \le 100\,000\).
• \(1 \le a_i, b_j \le 10^9\).

Sample Input

15
2
3 5
3
2 4 6

Sample Output

4

Explanation

Cho xưởng nặn làm \(9\) đơn vị thời gian: thợ \(1\) nặn \(3\), thợ \(2\) nặn \(1\), được \(4\) sản phẩm. Xưởng vẽ còn \(6\) đơn vị: thợ \(1\) vẽ \(3\), thợ \(2\) vẽ \(1\), thợ \(3\) vẽ \(1\), được \(5\) sản phẩm, nên hoàn thành \(4\) sản phẩm.