Problem Description

Score: $ 700 $ points

In Thistle's world, there are $ N $ companies, each manufacturing one type of computer. The performance of each computer improves exponentially, and the performance of the computer from company $ i $ ($1 \leq i \leq N$) exactly $ x $ years from now is $ a_i * b_i^{x-r_i} $.

Thistle has planned to replace his computer $ K $ times. On the $ i $-th replacement exactly $ y_i $ ($1 \leq i \leq K$) years from now, he will buy one of the computers with the highest performance at that time. If there are multiple computers with the highest performance, he can choose any one of them.

He wants to try computers from many companies, so he aims to maximize the number of different companies' computers he buys in the next $ K $ replacements. Determine the maximum number of different companies' computers he can buy.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ b_1 $ $ r_1 $ $ a_2 $ $ b_2 $ $ r_2 $ $ a_3 $ $ b_3 $ $ r_3 $ ... $ a_N $ $ b_N $ $ r_N $ $ K $ $ y_1 $ $ y_2 $ $ y_3 $ ... $ y_K $

Output Format

Output the maximum number of different companies' computers Thistle can buy in $ K $ replacements.

Sample Input and Output

Sample Input #1

3
4 2 0
2 4 0
1 6 0
3
0
1
2

Sample Output #1

3

Sample Input #2

3
10 10 2
8 2 0
8 4 1
3
0
3
5

Sample Output #2

3

Sample Input #3

3
10 10 0
5 5 0
2 2 0
3
0
5
10

Sample Output #3

1

Notes/Hints

Constraints

• $ N, K $ are integers between $ 1 $ and $ 200,000 $ inclusive.
• $ a_i $ is an integer between $ 1 $ and $ 200,000 $ inclusive.
• $ b_i $ is an integer between $ 2 $ and $ 200,000 $ inclusive.
• $ r_i $ is an integer between $ 0 $ and $ 200,000 $ inclusive.
• $ y_i $ is an integer between $ 0 $ and $ 200,000 $ inclusive.
• $ y_i $ ($1 \leq i \leq K - 1$)
• At the time of computer replacement, the performance of the best computer and the second-best computer is either the same or differs by at least $ 1 + 10^{-11} $ times. When there are multiple best computers, they are at least $ 1 + 10^{-11} $ times better than the next best. (Added at 16:06)

Subtasks

Subtask 1 \[ $ 200 $ points \]

• $N, K \leq 1,000$

Subtask 2 \[ $ 500 $ points \]

• No additional constraints.

见题面 Input 部分

见题面 Output 部分