問題文
蓟 在你的世界里, N 各公司 1 该公司生产不同类型的计算机。每种类型的计算机的性能都呈指数级提高,并且该公司 i (1 \leq i \leq N) 的电脑,刚才 x 一年后的表现是 a_i*{b_i}^{x-r_i} 。
Thistle,您正在使用您的计算机。 K 他打算买一个新的。 y_i (1 \leq i \leq K) 多年后 i 当您第一次购买新电脑时,请购买当时性能最高的电脑。 1 买一个。但是,如果您有多台性能最高的计算机,则可以购买其中任何一台。
他想使用许多公司的计算机,所以 从现在开始 K 购买替换他想要最大限度地增加计算机类型的数量。找出他可以购买的公司计算机的最大数量。
入力
输入以以下格式从标准输入提供。
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
出力
蓟你 K 输出一次替换购买中可以购买的计算机公司类型的最大数量。
制約
- N, K 是 您也可以写 1 以上 200 \ 000 的整数 给出了
- a_i 是 您也可以写 1 以上 200 \ 000 的整数 给出了
- b_i 是 您也可以写 2 以上 200 \ 000 的整数 给出了
- r_i 是 您也可以写 0 以上 200 \ 000 的整数 给出了
- y_i 是 您也可以写 0 以上 200 \ 000 的整数 给出了
- y_i < y_{i+1} (1 \leq i \leq K - 1)
- 购买新计算机时,性能最好和第二好的计算机的性能相同吗? 1+10^{-11} 是原来的两倍多。 1+10^{-11} 距离是两倍多。 (16:06 追記)
小課題
小課題1 [ 200点 ]
- N, K \leq 1 \ 000 很满意。
小課題2 [ 500点 ]
- 没有其他限制。
入力例1
3 4 2 0 2 4 0 1 6 0 3 0 1 2
出力例1
3
- 0 多年后,公司 1, 2, 3 每台计算机的性能为 4, 2, 1 。因此, 1 您下次购买业绩最高的公司 您可以购买一台 1 计算机。
- 1 多年后,公司 1, 2, 3 每台计算机的性能为 8, 8, 6 。因此, 2 您下次购买业绩最高的公司 您可以购买一台 1, 2 计算机。
- 2 多年后,公司 1, 2, 3 每台计算机的性能为 16, 32, 36 。因此, 3 您下次购买业绩最高的公司 您可以购买一台 3 计算机。
- 每次更换时,公司依次 1 -> 2 -> 3 当您购买电脑时, 3 您可以从不同的公司购买计算机。
入力例2
3 10 10 2 8 2 0 8 4 1 3 0 3 5
出力例2
3
- 0 多年后,公司 1, 2, 3 每台计算机的性能为 0.1, 8, 2 。因此, 1 您下次购买业绩最高的公司 您可以购买一台 2 计算机。
- 3 多年后,公司 1, 2, 3 每台计算机的性能为 100, 64, 128 。因此, 2 您下次购买业绩最高的公司 您可以购买一台 3 计算机。
- 5 多年后,公司 1, 2, 3 每台计算机的性能为 10000, 256, 2048 。因此, 3 您下次购买业绩最高的公司 您可以购买一台 1 计算机。
- 每次更换时,公司依次 2 -> 3 -> 1 当您购买电脑时, 3 您可以从不同的公司购买计算机。
入力例3
3 10 10 0 5 5 0 2 2 0 3 0 5 10
出力例3
1
在所有更换时,PC 1 具有最高的性能。因此,蓟 1 您只能购买不同公司的计算机。
作者: 秋鳗 通过重新排列获得的序列