G - パソコンの買い替え Editorial /

Time Limit: 2 sec / Memory Limit: 512 MB

配点： 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 < 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

全ての買い替え時において, パソコン 1 だけが最も性能が高い. よって Thistle 君は 1 種類の会社のパソコンしか買うことができない.

writer: autumn_eel