B'Adilbek has to water his garden. He is going to do it with the help of a complex watering system: he only has to deliver water to it, and the mechanisms will do all the remaining job. The watering system consumes one liter of water per minute (if there is no water, it is not working). It can hold no more than c liters. Adilbek has already poured c_0 liters of water into the system. He is going to start watering the garden right now and water it for m minutes, and the watering system should contain at least one liter of water at the beginning of the i -th minute (for every i from 0 to m - 1 ). Now Adilbek wonders what he will do if the watering system runs out of water. He called n his friends and asked them if they are going to bring some water. The i -th friend answered that he can bring no more than a_i liters of water; he will arrive at the beginning of the t_i -th minute and pour all the water he has into the system (if the system cannot hold such amount of water, the excess water is poured out); and then he will ask Adilbek to pay b_i dollars for each liter of water he has brought. You may assume that if a friend arrives at the beginning of the t_i -th minute and the system runs out of water at the beginning of the same minute, the friend pours his water fast enough so that the system does not stop working. Of course, Adilbek does not want to pay his friends, but he has to water the garden. So he has to tell his friends how much water should they bring. Formally, Adilbek wants to choose n integers k_1 , k_2 , ..., k_n in such a way that: Help Adilbek to determine the minimum amount he has to pay his friends or determine that Adilbek not able to water the garden for m minutes. You have to answer q independent queries. The first line contains one integer q ( 1 <= q <= 5 cdot 10^5 ) xe2 x80 x93 the number of queries. The first line of each quer'...