B"There are n chests. The i -th chest contains a_i coins. You need to open all n chests in order from chest 1 to chest n . There are two types of keys you can use to open a chest: You need to use in total n keys, one for each chest. Initially, you have no coins and no keys. If you want to use a good key, then you need to buy it. During the process, you are allowed to go into debt; for example, if you have 1 coin, you are allowed to buy a good key worth k=3 coins, and your balance will become -2 coins. Find the maximum number of coins you can have after opening all n chests in order from chest 1 to chest n . The first line contains a single integer t ( 1 <= q t <= q 10^4 ) -- the number of test cases. The first line of each test case contains two integers n and k ( 1 <= q n <= q 10^5 ; 0 <= q k <= q 10^9 ) -- the number of chests and the cost of a good key respectively. The second line of each test case contains n integers a_i ( 0 <= q a_i <= q 10^9 ) -- the amount of coins in each chest. The sum of n over all test cases does not exceed 10^5 . For each test case output a single integer -- the maximum number of coins you can obtain after opening the chests in order from chest 1 to chest n . Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++). In the first test case, one possible strategy is as follows: "...