Problem description

Bajtek codziennie przed szkołą odwiedza pobliski sklep z kanapkami. Kupuje w nim drugie śniadanie, które pozwala mu przetrwać wszystkie lekcje.

W sklepie sprzedawanych jest N rodzajów kanapek, ponumerowanych od 1 do N. Nie wszystkie z nich są dostępne każdego dnia. Przez kolejne Q dni, i‑tego dnia dostępne będą jedynie kanapki o rodzajach od A_i do B_i włącznie. Sklep jest bardzo popularny i chce obsłużyć jak najwięcej klientów, więc Bajtek może kupić każdy rodzaj kanapki co najwyżej raz dziennie.

Bajtek nie przejmuje się ceną kanapek, ale ma ograniczoną pojemność żołądka. Kanapka rodzaju j ma C_j kalorii. Natomiast Bajtek może zjeść co najwyżej X_i kalorii i-tego dnia.

Każda kanapka daje Bajtkowi pewną liczbę punktów satysfakcji. Zjedzenie kanapki j-tego rodzaju zapewnia mu S_j punktów satysfakcji. Satysfakcja Bajtka to po prostu suma punktów za wszystkie kanapki zjedzone przez niego danego dnia.

Dla każdego z Q dni pomóż Bajtkowi znaleźć maksymalną wartość jego satysfakcji, jaką może osiągnąć nie przekraczając limitu kalorii.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N – liczba rodzajów kanapek.

W każdym z kolejnych N wierszy znajdują się dwie liczby całkowite C_j i S_j – kaloryczność i punkty satysfakcji dawane przez j-tą kanapkę.

W następnym wierszu znajduje się jedna liczba całkowita Q – liczba dni.

W każdym z kolejnych Q wierszy znajdują się trzy liczby całkowite A_i, B_i i X_i – zakres dostępnych kanapek i pojemność żołądka Bajtka i-tego dnia.

Wyjście

Na wyjściu powinno znaleźć się Q wierszy.

W i-tym z nich powinna znaleźć się jedna liczba całkowita – maksymalna możliwa satysfakcja Bajtka i-tego dnia.

Ograniczenia

1 ≤ N ≤ 10 000,

1 ≤ C_j ≤ 2 000,

1 ≤ S_j ≤ 10⁹,

1 ≤ Q ≤ 100 000,

1 ≤ A_i ≤ B_i ≤ N,

1 ≤ X_i ≤ 2 000.

Podzadania

Przykład

6
2 2
1 3
4 4
3 5
2 3
3 2
3
1 6 7
2 4 4
5 6 3

11
8
3

5
1 2
2 3
3 4
4 5
5 6
1
1 5 15

20

5
2 2
3 3
4 4
5 5
6 6
1
1 5 1

0