\begin{problem}{Отели}{hotels.in}{hotels.out}{2 секунды}{256 мегабайт}

%Автор задачи: Евгений Замятин
%Автор условия: Евгений Замятин

Наконец закончив свои дела, Медвежонок, Заяц и Снежный брас встретились и решили обсудить место проживания на Олимпиаде.
Всего в олимпийской деревне построено $n$ отелей. Все они имеют различное количество <<звезд>>. Известно, что для любого 
целого числа $t$ такого, что $1 \le t \le n$ в деревне 
существует ровно один отель с таким количеством звезд.

Как известно, звери в отелях не самые желанные гости. Но для талисманов Олимпиады решили сделать исключение. Однако, чтобы
друзья особо не задерживались, администраторы решили сделать зверям не очень выгодное предложение:
каждый отель готов разместить у себя зверей при условии, что в первый день пребывания в отеле с $i$ звездами они 
заплатят $a_i$ рублей, а с каждым следующим днем стоимость номера в этом отеле отеле будет увеличиваться на $d_i$. 
Другими словами, стоимость номера в отеле с $i$ звездами
каждый день возрастает на $d_i$ вне зависимости от того, где сейчас живут звери. 
Такой расклад зверей, конечно, не устраивает, но выбора у них нет~--- 
%безысходность
ведь без них и Олимпиада не Олимпиада.

Зверей интересует, какую максимальную сумму им придется заплатить за день, если они хотят провести на олимпиаде 
ровно $k$ дней в отелях, количество звезд в которых не меньше $l$ и не больше $r$. При этом, каждый из этих дней они будут выбирать 
самый дешевый отель из возможных. Помогите им ответить на несколько таких вопросов!
 
\InputFile
В первой строке входного файла задано число $n$ ($1 \le n\le 100{\,}000$)~--- количество отелей.
Далее идут $n$ строк по два числа $a_i$ и $d_i$ ($1 \le a_i, d_i \le 1{\,}000{\,}000{\,}000$)~--- описание $i$-звездочного отеля.
Затем задано число $t$ ($1 \le t \le 100{\,}000$)~--- количество запросов.
В следующих $t$ строках записано по три числа $l_i$, $r_i$ и $k_i$($1 \le l_i, r_i \le n, 1 \le k_i \le 1{\,}000{\,}000{\,}000$)~--- 
описание $i$ого запроса.

\OutputFile
Выведите $t$ строк~--- ответ на задачу.

\Examples
\begin{example}%
\exmp{
2
1 4
3 1
2
1 1 3
1 2 3
}{
9
5
}%
\end{example}

\Note:
Решения, работающие для $n, k_i \le 100, t \le 10$, будут оцениваться в $20$ баллов.

Решения, работающие для $t = 1$, будут оцениваться в $20$ баллов.

\end{problem}
