고인물의 두번째 리듬게임

리듬게임 국가대표, 월드컵 준결승의 주역인 고인물 카루나는 리듬게임을 제패하기 위해 새로운 리듬게임을 시작했다. 

카루나가 플레이할 곡은 여러 개의 노트로 이루어져 있다. 각 노트는 곡의 시작으로부터 정확히 $T\_i$초 후에 쳐야 하며, 치면 점수 $A\_i$와 에너지 $B\_i$를 얻는다. 모든 노트에 대해 얻은 점수의 총합이 최종 점수가 된다. $A\_i$가 음수일 수도 있지만, 카루나는 그런 걸 신경쓰지 않고 항상 모든 노트를 정확한 시간에 친다.

추가로, 이 게임은 피버라는 시스템을 가지고 있다. 곡이 시작할 때의 피버 게이지는 0이고, 노트를 칠 때마다 얻은 에너지만큼 피버 게이지가 차오른다. 단, 피버 게이지가 $X$를 초과하면 $X$로 고정된다.

피버 게이지가 $X$만큼 찼을 때, 카루나는 아무 때나 피버 타임을 발동시킬 수 있다. 피버 타임은 정확히 $Y$초 동안 진행되며, 피버 타임 동안 처리되는 노트의 점수는 2배가 된다. 피버 타임이 시작되거나 끝남과 동시에 처리되는 노트에 대해서도 2배의 점수를 얻는다. 피버 타임 동안 피버 게이지는 차오르지 않으며, 피버 타임이 끝난 직후 피버 게이지는 0으로 초기화된다.

이 게임에는 여러 개의 난이도가 있고, 각 난이도마다 최대 피버 게이지 $X$와 피버 타임의 길이 $Y$가 다르다. 각 난이도마다 카루나가 얻을 수 있는 최대 점수를 구해보자!

입력의 첫 줄에 노트의 개수 $N$이 주어진다.

뒤따르는 $N$개의 줄에는 각 노트의 등장 시각 $T\_i$, 점수 $A\_i$, 에너지 $B\_i$가 주어진다. 노트의 등장 시간 $T\_i$는 모두 다름이 보장된다.

다음으로 난이도의 개수 $Q$가 주어진다.

뒤따르는 $Q$개의 줄에는 각 난이도의 최대 피버 게이지 $X\_i$와 피버 타임의 길이 $Y\_i$가 주어진다.

$Q$개의 줄에 걸쳐 각 난이도에서 얻을 수 있는 최대 점수를 출력한다.

• $1 \leq N \leq 1,000,000$
• $1 \leq Q \leq 10$
• $0 \leq T\_i, B\_i \leq 10^9$
• $-10^9 \leq A\_i \leq 10^9$
• $1 \leq X\_i, Y\_i \leq 10^9$
• 입력으로 주어지는 모든 수는 정수이다.