Nhà máy Binary

Điểm số: 1

Giới hạn thời gian: 1s

Giới hạn bộ nhớ: 512 MB

Người đăng: ICTU

Nhà máy Binary có một loạt các công việc được sắp xếp trên một cây nhị phân hoàn chỉnh có độ cao là h. Có w công nhân, mỗi công nhân trong một giờ chỉ thực hiện được 1 công việc từ gốc của cây nhị phân đó. Tại thời điểm đầu tiên chỉ có sẵn một công việc tại gốc của cây, do đó chỉ có 1 công nhân có việc để làm. Tại các thời điểm tiếp theo các công nhân sẽ lần lượt tham gia giải quyết các công việc có sẵn còn lại trên cây nhị phân. Hãy tính toán thời gian ngắn nhất để các công nhân hoàn thành hết công việc trên cây này.

            Đầu vào

Dòng đầu tiên là một số t (1 <= t <= 5 * 105) là số lượng test case. Một t dòng tiếp theo bao gồm 2 số h (1 <= h <= 50) là độ cao của cây nhị phân và w (1<= w <= 104) là số lượng công nhân.

            Đầu ra

Đầu ra của mỗi test case là một số nguyên duy nhất là thời gian nhỏ nhất để các công nhân hoàn thành cây nhị phân

            Ví dụ

Đầu vào

Đầu ra

3

3 1

3 2

10 6

7

4

173

            Giải thích

            Tại ví dụ 2, ban đầu chỉ thực hiện 1 công nhân làm việc, những lần sau thì cả 2 công nhân cùng làm việc.