Let's Go to Jinju! (Hard)

This problem is the same as "Let's Go to Jinju! (Easy)" except for the range of the input numbers. Be sure to check the language and memory limits.

Boseon, a Gyeongsang National University graduate worn out by life in Seoul, misses the college years and wants to visit Jinju, where the university is. So Boseon went straight to the Seoul bus terminal to make a day trip to Jinju.

The Seoul terminal has $N$ transportation options. Each option has a destination and a fare, and all destinations are distinct. The destinations always include jinju, which is the option going to Jinju.

With prices rising, Boseon wants to know the fare to Jinju and how many options cost more than that. Boseon is too exhausted to check all $N$ options, so Boseon asks us to find this information.

Now, help Boseon out.

The first line contains $N$, the number of transportation options at the Seoul terminal. ($1 \le N \le 5\,000\,000$)

From the second line, the next $N$ lines each contain $D_i$ and $C_i$, separated by a space. $D_i$ is the destination of the $i$-th option, a string of 1 to 15 lowercase English letters. Exactly one $j$ has $D_j =$ jinju, meaning the $j$-th option goes to Jinju. $C_i$ is the fare of the $i$-th option. ($1 \le C_i \le 10^{15}$; $1 \le C_j \le 1\,000$)

All numbers in the input are integers.

The first line prints the fare of the option to Jinju.

The second line prints the number of options that cost more than the option to Jinju.

The input is very large, so use fast input and output methods.