sellCandies2

Lưu ý: Đây là phiên bản khó hơn của bài sellCandies1. Điểm khác biệt ở đây là giới hạn của n và giới hạn thời gian.

Lee có vô hạn các túi kẹo lần lượt chứa 6, 9 và 20 cái kẹo. Có 1 khách hàng muốn mua n cái kẹo, Lee muốn bán được nhiều túi kẹo nhất có thể. Hãy giúp Lee tính số túi kẹo tối đa bán được, biết rằng cô sẽ không được bán lẻ từng cây kẹo. Nếu không thể bán đủ kẹo trả về -1.

Ví dụ: 

• Với n = 18 thì sellCandies(n) = 3.
  Giải thích: ta có thể bán 3 túi 6.
• Với n = 77 thì sellCandies(n) = 10.
  Giải thích: ta có thể bán 8 túi 6, 1 túi 9 và 1 túi 20.
• Với n = 63 thì sellCandies(n) = 10.
  Giải thích: ta bán 9 túi 6 và 1 túi 9.

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

• [Thời gian chạy]: 0.1 giây với C++, 0.6 giây với Java và C#, 0.8 giây với Python, GO và Js.

• [Đầu vào] integer
  1 ≤ n ≤ 10^7
• [Đầu ra]integer