#CSPS2020D. 贪吃蛇 (Greedy Snake)

贪吃蛇 (Greedy Snake)

Description

There are nn snake on the grass, numbered from 11 to nn, respectively. At the begining, stamina of each snake is aia_i. We call the snake numbered xx stronger than the one with number yy if its current stamina is greater than the other one (ax>aya_x > a_y), or ax=aya_x = a_y and x>yx > y.

Then, these snakes will have a duel. The duel will continue for several rounds. In each round, the strongest snake will have two options:

  1. It will eat the weakest snake and its stamina will decreased by the stamina of that weakest snake. The eaten snake will be removed from the duel.
  2. It won't eat any snake, the duel will end immediately.

Each snake wants to maximize the number of snake they eat without being eaten (obviously, snakes won't eat themselves).

Suppose every snake is smart enough, calculate the number of snake left after the duel.

This problem has multiple sets of data. For the first set of data, the stamina of each snake will be given in the input. For each subsequent set of data, some snakes' stamina will be changed.

Input Format

The first line contains an integer TT, the number of dataset.
The following line contains a single integer nn, the number of snakes.
The third line will contains exactly nn integers, the ii-th number represents the ii-th snake's initial stamina.
The next T3T - 3 lines contains T1T - 1 dataset, each dataset will have the following format:

  • One line contains an integer kk, the number of snakes whose stamina will be changed.
  • One line contains 2k2k integers and every two integers form a pair (x,y)(x, y) which means that the snake number xx's stamina will become yy.

Output Format

Print exactly TT lines, each represents the number of snakes left after the duel ends with the data provides in the ii-th dataset.

2
3
11 14 14
3
1 5 2 6 3 25
3
1
2
5
13 31 33 39 42
5
1 7 2 10 3 24 4 48 5 50
5
3

Sample 3

See attached files snakes3.in and snakes3.in

Sample 4

See attached files snakes4.in and snakes4.in

Constraints

For 20%20\% of data, n=3n=3.
For 40%40\% of data, n10n \le 10.
For 55%55\% of data, n2×103n \le 2 \times 10^3.
For 70%70\% of data, n5×104n \le 5 \times 10^4.
For 100%100\% of data, 3n106,1T10,0k105,0ai,y1093 \le n \le 10^6, 1 \le T \le 10, 0 \le k \le 10^5, 0 \le a_i, y \le 10^9.
It's guaranteed that in every dataset, aia_i will be arranged in non-decreasing order.