#1416. GREEN - Bầu cử

Trong cuộc bầu cử tổng thống Mỹ còn lại 2 ứng viên: bố già Sam và bố già Frodo. Bạn làm việc trong đội của bố già Sam và cần giúp cho bố thắng cử.

Theo nguyên tắc để thắng cử thì bố già Sam cần phải có nhiều hơn số phiếu. Nhưng trên thực tế thì cần ít hơn nhiều. Như thế này nhé:

Như ta đã biết thì Mỹ chia ra làm các tiểu bang. Lúc bắt đầu ở các tiểu bang sẽ tổ chức các cuộc bầu cử địa phương, rồi lấy kết quả để tiểu bang bỏ phiếu bầu cho trong ứng viên. Nếu như không ít hơn một nửa số tiểu bang bầu cho bố già Sam thì bố thắng (nếu số phiếu bằng nhau thì bố vẫn thắng), còn không thì bố già Frodo thắng. Mỗi tiểu bang lại được chia thành các vùng khác nhau, rồi các vùng lại chia thành các vùng nhỏ hơn, và cứ thế chia tiếp. Vùng nhỏ nhất chính là các vùng chỉ chứa cư dân Mỹ. Ở Mỹ chỉ có người dân và bậc theo cách chia vùng. Theo nguyên tắc công bằng thì tất cả vùng bậc cũng phải chia ra làm các vùng bậc tiếp theo với số lượng bằng nhau (và có dân số bằng nhau).

Kì diệu ở chỗ là việc chia vùng lại phụ thuộc vào bạn, tức là vùng bậc chia thành bao nhiêu vùng bậc nằm trong tay bạn.

Ngoài ra bạn có thể thao túng kết quả bầu cử thông qua dầu mỏ. Để mua phiếu cho bố già Sam từ cử tri thì chỉ cần trả cho anh ta thùng dầu.

Nhưng tệ ở một chỗ là từ đầu cả nước lại muốn bầu cho bố già Frodo. Hãy tính chi phí ít nhất để mua chuộc cử tri cho bố già Sam.

Dữ liệu vào:

• Một dòng duy nhất chứa hai số nguyên và .

Dữ liệu ra:

• Ghi ra một số duy nhất là chi phí nhỏ nhất để mua chuộc kết quả.

Ví dụ:

Dữ liệu vào:

9 2

Dữ liệu ra:

4

Dữ liệu vào:

12 3

Dữ liệu ra:

2

Giới hạn:

• Subtask số điểm có :
• Subtask số điểm khác có ;
• Subtask số điểm khác có ;
• Subtask số điểm còn lại không có ràng buộc bổ sung.