Адилбеку нужно полить свой сад. Он собирается сделать это с помощью сложной системы полива: ему нужно только доставить воду, а механизмы выполнят всю оставшуюся работу.

Система полива потребляет один литр воды в минуту (если воды нет, она не работает). Она может вместить не более $$$c$$$ литров воды. Адилбек уже налил в систему $$$c_0$$$ литров воды. Он собирается начать поливать сад прямо сейчас и поливать его в течение $$$m$$$ минут, а система полива должна содержать не менее одного литра воды в начале $$$i$$$-й минуты (для каждого $$$i$$$ от $$$0$$$ до $$$m - 1$$$).

Адилбеку интересно, что он будет делать, если в системе полива кончится вода. Он позвонил $$$n$$$ своим друзьям и спросил их, могут ли они принести воды. $$$i$$$-й друг ответил, что он может принести не более $$$a_i$$$ литров воды; он придет в начале $$$t_i$$$-й минуты и выльет всю воду, которая у него есть, в систему (если система не может вместить такое количество воды, избыток воды выливается); а затем он попросит Адилбека заплатить $$$b_i$$$ долларов за каждый литр воды, который он принес. Можете считать, что если друг прибывает в начале $$$t_i$$$-й минуты, а в начале той же минуты в системе заканчивается вода, друг наливает воду достаточно быстро, чтобы система не перестала работать.

Конечно, Адилбек не хочет платить своим друзьям, но ему нужно поливать сад. Поэтому он должен сказать своим друзьям, сколько воды они должны принести. Формально Адилбек хочет выбрать $$$n$$$ целых чисел $$$k_1$$$, $$$k_2$$$, ..., $$$k_n$$$ таким образом, чтобы:

• если друг $$$i$$$ приносит ровно $$$k_i$$$ литров воды, то система полива работает в течение всего времени, необходимого для полива сада;
• сумма $$$\sum\limits_{i = 1}^{n} k_i b_i$$$ минимально возможна.

Помогите Адилбеку определить минимальную сумму, которую он должен заплатить своим друзьям, или определите, что Адилбеку не удастся поливать сад в течение $$$m$$$ минут.

Вам нужно ответить на $$$q$$$ независимых запросов.