P16765 [GKS 2020 #E] Toys

Little Axel has $N$ toys numbered from $1$ to $N$. Each toy has $2$ properties: - $E_i$—enjoyment, which is the number of minutes Axel can play with toy number $i$ without getting bored with it; - $R_i$—remembrance, which is the number of minutes it takes Axel to forget toy number $i$ after having played with it. The toys are arranged in a circle, from $1$ to $N$ clockwise. Axel plays with them one by one. When Axel reaches toy $i$ which he has not played with yet, or which he has already forgotten about, he plays with it for $E_i$ minutes and then immediately moves to the next one (clockwise). If he reaches a toy that he has not forgotten yet (if less than $R_i$ minutes have passed since the last time he finished playing with it), he will stop and cry. We can define the time Axel spent playing as the sum of $E_i$ of every toy Axel played with before stopping. If Axel played with a toy several times, it should be counted that many times. Given the description of the toys, remove the smallest possible number of them in order to make Axel play either an indefinitely long time, or (if that is not possible) as long as possible before he stops. **Note:** - Axel has never played with these toys before; - he cannot be left without toys; - he always starts with the toy that has the smallest number; - after finishing playing with the toy that has the largest number, he will move to the toy that has the smallest number.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line containing the integer $N$. Next $N$ lines contain $2$ integers each: $E_i$ and $R_i$. The $i$-th line is describing the toy number $i$.

For each test case, output one line containing `Case #x: y z`, where: - $x$ is the test case number (starting from $1$); - $y$ is the longest time Axel will play in minutes or `INDEFINITELY` (without quotes) if he will play indefinitely long time. - $z$ is the minimal number of toys to remove so that Axel could play with the rest of them either indefinitely or as long as possible;

In Sample Case #$1$ there is only $1$ toy, so Axel will play with it and will get bored in $5$ minutes. In Sample Case #$2$, after playing with the toy number $1$ for $5$ minutes, he will need to not play with it for $10$ minutes, which he will spend playing with the toy number $2$. After that he will return to the toy number $1$ and play with it for $5$ minutes, during which he will forget the toy number $2$, and so on. Thus he will play for an indefinitely long time. In Sample Case #$3$, although Axel can play with the toy number $1$ for $30$ minutes, if we remove it he will be able to play with the others indefinitely. So we remove it, and keep the other two. In Sample Case #$4$, Axel will play with the toys in the following order: $1$, $2$, $3$, $1$, $2$, and then he will stop and cry as he still remembers the toy number $3$. So, in total he will play for $25$ minutes. ### Limits $1 \le T \le 100$. $1 \le E_i \le 10^9$. $1 \le R_i \le 10^9$. **Test Set $1$** $1 \le N \le 12$. **Test Set $2$** $1 \le N \le 10^5$.