CF2240A Another Popcount Problem

You are given two integers $ n $ and $ k $ . Your task is to construct a sequence $ a $ consisting of $ k $ non-negative integers $ a_1, a_2, \ldots, a_k $ such that: - $ \sum_{i=1}^{k} a_i \le n $ - The total number of set bits, i.e., $ \sum_{i=1}^{k} \operatorname{popcount}(a_i) $ , is as large as possible. You only need to output the maximum possible value of $ \sum_{i=1}^{k} \operatorname{popcount}(a_i) $ . Here, $ \operatorname{popcount}(x) $ denotes the number of $ 1 $ bits in the binary representation of $ x $ . For example, $ \operatorname{popcount}(6) = \operatorname{popcount}((110)_2) = 2 $ , and $ \operatorname{popcount}(0) = 0 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^3 $ ). The description of the test cases follows. Each of the next $ t $ lines contains two integers $ n $ and $ k $ ( $ 1 \le n, k \le 10^6 $ ) — the maximum allowed sum of the sequence and the length of the sequence, respectively.

For each test case, output a single integer — the maximum possible value of $ \sum_{i=1}^{k} \operatorname{popcount}(a_i) $ .

In the first test case, $ n=2 $ and $ k=1 $ . We can choose $ a = [1] $ or $ a = [2] $ . In both cases, the sum of popcounts is $ 1 $ . In the second test case, $ n=3 $ and $ k=1 $ . We can choose $ a = [3] $ , since $ (3)_2 = (11)_2 $ , $ \operatorname{popcount}(3) = 2 $ . In the third test case, $ n=6 $ and $ k=2 $ . We can choose $ a = [3, 3] $ . The sum is $ 3 + 3 = 6 \le 6 $ , and the total popcount is $ \operatorname{popcount}(3) + \operatorname{popcount}(3) = 2 + 2 = 4 $ .