buySquare

Vũ “Maripium” Hoàng Kiên là một bác sĩ phẫu thuật, nhưng đồng thời bác sĩ cũng rất thích tham gia vào ngành bất động sản. Bác sĩ đang có n nghìn đô và muốn mua một số mảnh đất hình vuông bằng số tiền này, biết rằng mảnh đất có độ dài cạnh là a ha thì có giá là a2 nghìn đô. Bác sĩ muốn tiêu hết toàn bộ n nghìn đô này và cũng đồng thời mua ít mảnh đất nhất có thể. Hãy cho bác sĩ biết số mảnh đất mà bác sĩ sẽ mua.

Ví dụ:

• Với n = 344, bác sĩ sẽ mua tối thiểu 3 mảnh đất với kích thước lần lượt là 18 x 18, 4 x 4 và 2 x 2 ha. Tổng giá tiền của 3 mảnh đất là 182 + 42 + 22 = 344 nghìn đô.

Đầu vào/Đầu ra:

• [Giới hạn thời gian chạy] 0.5 giây với C++, 3 giây với Java và C#, 4 giây với Python, Go và Js.
• [Đầu vào] Integer n
  1 <= n <= 60000
• [Đầu ra] Integer
  Trả về số mảnh đất tối thiểu mà bác sĩ cần mua để tiêu hết số tiền này.