Tiểu D gần đây tìm thấy một trò chơi nhỏ trên mạng. Luật chơi như sau:
- Mục tiêu là giết $n$ con rồng theo thứ tự đánh số $1\sim n$. Mỗi con rồng có lượng máu ban đầu $a_i$. Mỗi con còn có khả năng hồi phục: khi sử dụng khả năng này, máu của nó tăng thêm $p_i$ sau mỗi lần hồi phục cho đến khi không âm. Nó chỉ chết khi cuộc tấn công đã kết thúc và lượng máu bằng đúng $0$.
- Khi trò chơi bắt đầu, người chơi có $m$ thanh kiếm với sức tấn công đã biết. Mỗi lần đối mặt với một con rồng, người chơi chỉ được chọn một thanh kiếm. Sau khi giết rồng, thanh kiếm này biến mất, nhưng người chơi nhận được một thanh kiếm mới làm phần thưởng.
Tiểu D thấy trò chơi này rất nhàm chán, nhưng người chơi hoàn thành nhanh nhất có thể giành quyền tham dự ION2018. Vì vậy, cô quyết định viết một rô-bốt ngốc nghếch để giúp mình hoàn thành trò chơi. Rô-bốt của cô tuân theo các quy tắc sau:
- Mỗi lần đối mặt với một con rồng, rô-bốt chọn thanh kiếm có sức tấn công lớn nhất trong số các thanh kiếm đang sở hữu có sức tấn công không vượt quá lượng máu ban đầu của rồng. Nếu không có thanh kiếm như vậy, nó chọn thanh kiếm có sức tấn công nhỏ nhất.
- Với mỗi con rồng, rô-bốt dùng thanh kiếm đã chọn ở bước trên tấn công đúng $x$ lần cố định, làm máu rồng giảm $x\times ATK$.
- Sau đó, rồng liên tục sử dụng khả năng hồi phục, mỗi lần hồi $p_i$ máu. Nếu lượng máu bằng $0$ trước khi hồi phục hoặc sau một lần hồi phục nào đó, rồng chết và người chơi vượt qua màn này.
Rõ ràng, số lần tấn công của rô-bốt là yếu tố quyết định việc hoàn thành trò chơi nhanh nhất. Tiểu D giờ đã biết tất cả thuộc tính của mọi con rồng và muốn thử tài bạn: phải đặt số lần tấn công $x$ của rô-bốt là bao nhiêu để hoàn thành trò chơi với ít lần tấn công nhất?
Tất nhiên, nếu không thể hoàn thành trò chơi với bất kỳ giá trị nào thì chỉ cần in ra -1.
Dữ liệu vào
Đọc dữ liệu từ tệp dragon.in.
Dòng đầu tiên chứa một số nguyên $T$, là số bộ dữ liệu.
Tiếp theo là $T$ bộ dữ liệu, mỗi bộ gồm 5 dòng.
- Dòng đầu tiên của mỗi bộ chứa hai số nguyên $n$ và $m$, là số con rồng và số thanh kiếm ban đầu;
- Dòng tiếp theo chứa $n$ số nguyên dương, số thứ $i$ là lượng máu ban đầu $a_i$ của con rồng thứ $i$;
- Dòng tiếp theo chứa $n$ số nguyên dương, số thứ $i$ là khả năng hồi phục $p_i$ của con rồng thứ $i$;
- Dòng tiếp theo chứa $n$ số nguyên dương, số thứ $i$ là sức tấn công của thanh kiếm được thưởng sau khi giết con rồng thứ $i$;
- Dòng tiếp theo chứa $m$ số nguyên dương, là sức tấn công của $m$ thanh kiếm ban đầu.
Dữ liệu ra
Ghi kết quả vào tệp dragon.out.
Gồm tổng cộng $T$ dòng.
Dòng thứ $i$ chứa một số nguyên, là số lần tấn công $x$ nhỏ nhất giúp rô-bốt hoàn thành trò chơi đối với bộ dữ liệu thứ $i$. Nếu không tồn tại đáp án, in ra -1.
Ví dụ
Dữ liệu vào 1
2 3 3 3 5 7 4 6 10 7 3 9 1 9 1000 3 2 3 5 6 4 8 7 1 1 1 1 1
Dữ liệu ra 1
59 -1
Ghi chú
Bộ dữ liệu thứ nhất:
- Ban đầu, sức tấn công của các thanh kiếm là $\{1,9,10\}$. Con rồng thứ $1$ có $3$ máu nên chọn thanh kiếm có sức tấn công $1$. Tấn công $59$ lần, gây $59$ sát thương, khiến máu rồng còn $-56$. Sau $14$ lần hồi phục, máu bằng đúng $0$ và rồng chết.
- Thanh kiếm có sức tấn công $1$ biến mất, nhận một thanh kiếm có sức tấn công $7$. Lúc này sức tấn công của các thanh kiếm là $\{7,9,10\}$. Con rồng thứ $2$ có $5$ máu nên chọn thanh kiếm có sức tấn công $7$. Tấn công $59$ lần, gây $413$ sát thương, khiến máu rồng còn $-408$. Sau $68$ lần hồi phục, máu bằng đúng $0$ và rồng chết.
- Lúc này sức tấn công của các thanh kiếm là $\{3,9,10\}$. Con rồng thứ $3$ có $7$ máu nên chọn thanh kiếm có sức tấn công $3$. Tấn công $59$ lần, gây $177$ sát thương, khiến máu rồng còn $-170$. Sau $17$ lần hồi phục, máu bằng đúng $0$ và rồng chết.
- Không có cách hoàn thành nào dùng ít hơn $59$ lần tấn công, nên đáp án là $59$.
Bộ dữ liệu thứ hai:
- Không có cách nào giết được cả con rồng thứ nhất lẫn con rồng thứ hai, nên không thể hoàn thành trò chơi và in ra
-1.
Ví dụ 2
Xem các tệp dragon/dragon2.in và dragon/dragon2.ans trong thư mục của thí sinh.
Nhiệm vụ con
| Số hiệu bộ kiểm thử | $n$ | $m$ | $p_i$ | $a_i$ | Sức tấn công | Giới hạn khác |
|---|---|---|---|---|---|---|
| $1\sim2$ | $\le10^5$ | $=1$ | $=1$ | $\le10^5$ | $=1$ | Không có |
| $3\sim4$ | $\le10^5$ | $=1$ | $=1$ | $\le10^5$ | $\le10^5$ | Không có |
| $5\sim7$ | $\le10^3$ | $\le10^3$ | $\le10^5$ | $\le10^5$ | $\le10^5$ | Tính chất 1, tính chất 2 |
| $8\sim13$ | $=1$ | $=1$ | $\le10^8$ | $\le10^8$ | $\le10^6$ | Tính chất 1 |
| $14\sim15$ | $=10^5$ | $=10^5$ | $=1$ | $\le10^8$ | $\le10^6$ | Không có giới hạn đặc biệt |
| $16\sim17$ | $\le10^5$ | $\le10^5$ | Mọi $p_i$ đều là số nguyên tố | $\le10^{12}$ | $\le10^6$ | Tính chất 1 |
| $18\sim20$ | $\le10^5$ | $\le10^5$ | Không có giới hạn đặc biệt | $\le10^{12}$ | $\le10^6$ | Tính chất 1 |
Tính chất 1: Với mọi $i$, $a_i\le p_i$.
Tính chất 2: $\operatorname{LCM}(p_i)\le10^6$, tức là bội chung nhỏ nhất của tất cả $p_i$ không vượt quá $10^6$.
Với mọi bộ kiểm thử, $T\le5$, sức tấn công của mọi vũ khí không vượt quá $10^6$, và bội chung nhỏ nhất của tất cả $p_i$ không vượt quá $10^{12}$.
Ghi chú
Các kết quả trung gian mà bạn sử dụng có thể rất lớn. Hãy chú ý kiểu của các biến lưu trữ kết quả trung gian.