Một vương quốc đang bị đe dọa bởi con rồng. Mỗi con rồng có một cái đầu với đường kính nhất định. Để cứu vương quốc, nhà vua đã thuê hiệp sĩ. Mỗi hiệp sĩ có một chiều cao nhất định. Một hiệp sĩ có chiều cao có thể chém được một cái đầu rồng có đường kính nếu . Mỗi hiệp sĩ chỉ có thể chém một cái đầu rồng.
Để thuê một hiệp sĩ, nhà vua phải trả một số tiền vàng bằng đúng chiều cao của hiệp sĩ đó. Hãy giúp nhà vua chọn các hiệp sĩ để chém đầu tất cả các con rồng với tổng chi phí là ít nhất.
Dữ liệu:
Gồm nhiều bộ test.
Mỗi bộ test gồm:
Dòng đầu tiên chứa hai số nguyên và .
Dòng thứ hai chứa số nguyên là đường kính đầu của con rồng.
Dòng thứ ba chứa số nguyên là chiều cao của hiệp sĩ.
Dữ liệu kết thúc khi và .
Kết quả:
Với mỗi bộ test, in ra tổng chi phí nhỏ nhất để thuê các hiệp sĩ chém hết rồng.
Nếu không thể chém hết tất cả các con rồng (ví dụ, số hiệp sĩ không đủ hoặc không có hiệp sĩ nào đủ cao), in ra "Loowater is doomed!".
Ví dụ:
Dữ liệu:
2 3
5 4
7 8 4
2 1
5 5
5
0 0
Kết quả:
11
Loowater is doomed!
Giải thích:
Ví dụ 1: Có 2 rồng (đường kính 4, 5) và 3 hiệp sĩ (cao 4, 7, 8).
Để chém đầu rồng đường kính 4, ta chọn hiệp sĩ thấp nhất có thể là hiệp sĩ cao 4 (chi phí 4).
Để chém đầu rồng đường kính 5, ta chọn hiệp sĩ thấp nhất còn lại có thể là hiệp sĩ cao 7 (chi phí 7).
