너지몬 GO

너지몬 GO는 너지몬을 잡고 진화시켜서 경험치(XP)를 최대한 많이 모으는 게임이다. 너지몬을 한 마리 잡으면 100 XP, 너지몬을 한 번 진화시키면 500 XP를 얻는다. 요즘 친구가 이 게임을 자주 하는데, 당신은 친구의 전략이 최적이 아니라고 생각한다.

모든 너지몬은 여러 계열로 나뉘고, 계열마다 고유한 사탕 종류가 있다. 한 계열의 너지몬은 가장 약한 것부터 가장 강한 것까지 순서가 매겨져 하나의 사슬을 이룬다. 계열에서 가장 강한 너지몬이 아니라면 같은 계열의 바로 다음 순위 너지몬으로 진화시킬 수 있다.

사탕은 너지몬 세계의 기본 화폐다.

• 너지몬을 잡으면 그 너지몬 계열의 사탕을 3개 얻는다.
• 너지몬을 되돌릴 수 없게 방출하면 그 너지몬 계열의 사탕을 1개 얻는다.

너지몬을 진화시킬 때마다 그 계열의 사탕이 정해진 개수만큼 소모된다. 또한 계열 사슬을 따라 진화 비용은 감소하지 않는다. 즉 계열 안에서 순위가 높은 진화는 낮은 진화보다 비용이 같거나 크다.

다음은 가능한 너지몬 진화의 예시다.

개발사에 돈을 벌어 주는 것과 너지몬을 몽땅 잡는 것 외에도, 이 게임의 목표는 경험치를 최대한 많이 모아 캐릭터의 레벨을 올리고 야생에서 더 강한 너지몬을 만나는 것이다. 첫 번째 목표와도 맞물려서 게임 안에서는 현금으로 축복의 알을 살 수 있다. 축복의 알을 활성화하면 그 뒤 30분 동안 얻는 경험치가 두 배가 된다. 즉 게임 시작 후 $e$초에 알을 활성화했다면 시각 $t$에 한 행동은 $e \le t < e + 1800$일 때, 그리고 그때만 경험치를 두 배로 얻는다.

친구는 게임을 시작할 때 축복의 알을 하나 받았지만 완전히 낭비해 버렸다. 당신은 축복의 알이 활성화되어 있는 동안에만 너지몬을 진화시키는 것이 낫고, 그렇지 않으면 자원을 크게 낭비한다고 생각한다. 이를 친구에게 증명하려고 친구가 잡은 모든 너지몬의 기록을 시각과 함께 받아 두었다. 친구가 축복의 알을 활성화할 시각을 전략적으로 골랐고 알이 활성화된 동안에만 너지몬을 진화시켰다면 지금 가지고 있을 수 있었던 경험치의 최댓값을 구하자.

입력은 다음과 같이 이루어진다.

• 첫째 줄에 너지몬 계열의 수를 나타내는 정수 $f$ ($0 \le f \le 10^5$)가 주어진다.
• 다음 $f$개의 줄에 너지몬 계열이 하나씩 주어진다. 각 줄은 다음 요소로 이루어진다.
  • 이 계열의 너지몬 수를 나타내는 정수 $s_i$ ($1 \le s_i \le 10^5$)
  • 너지몬의 이름과, 그 너지몬을 진화시킬 때 소모되는 (해당 종류의) 사탕 개수를 나타내는 정수 $c_j$ ($1 \le c_j \le 10^5$)의 쌍 $s_i - 1$개
  • 이 계열에서 가장 강한 너지몬의 이름
• 다음 줄에 친구가 잡은 너지몬의 수를 나타내는 정수 $n$ ($0 \le n \le 4 \times 10^5$)이 주어진다.
• 다음 $n$개의 줄에 정수 $t_i$ ($0 \le t_i \le 10^9$)와 문자열 $p_i$가 주어진다. 각각 너지몬을 잡은 시각과 잡은 너지몬의 이름이다.

너지몬의 종류는 최대 $10^5$개이다 ($\sum_i s_i \le 10^5$). 각 계열의 너지몬은 순위가 오르는 순서로 주어지므로 한 계열 안의 $c$ 값은 감소하지 않는다. 모든 너지몬 이름은 알파벳 소문자 1개 이상 20개 이하로 이루어진 문자열이다. 시각 $t_i$는 감소하지 않는다(친구는 무척 빨라서 같은 초에 너지몬을 여러 마리 잡을 수 있다). 한 계열 안에서나 여러 계열에 걸쳐서 같은 너지몬 이름이 두 번 이상 나오지 않고, 잡은 $n$마리의 너지몬은 모두 주어진 계열 중 하나에 속한다.

친구가 최적의 시각에 축복의 알을 활성화했고 알이 활성화된 동안에만 너지몬을 진화시켰다면 현재 시점에 가지고 있을 수 있었던 경험치의 최댓값을 출력한다.