AT_tkppc3_g パソコンの買い替え

[problemUrl]: https://atcoder.jp/contests/tkppc3/tasks/tkppc3_g 配点： $ 700 $ 点 Thistle 君の世界では, $ 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 $

Thistle 君が $ 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\ (1\ \leq\ i\ \leq\ K\ -\ 1 $) - **パソコンの買い替え時において, 一番性能の良いパソコンと二番目に性能が良いパソコンの性能は同じか, $ 1+10^{-11} $ 倍以上離れている. 一番性能の良いパソコンが同率で複数台あるときも、それより下とは $ 1+10^{-11} $ 倍以上離れている.** (16:06 追記) ### 小課題 小課題1 \[ $ 200 $点 \] - $ N,\ K\ \leq\ 1\ 000 $ を満たす. 小課題2 \[ $ 500 $点 \] - 追加の制約はない.