D - Part-Time Job Shift Assignment Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は学園祭の実行委員長を務めており、N 人のアルバイトスタッフを雇っています。各スタッフ i (1 \leq i \leq N) には、1時間あたりにこなせる作業量を表す作業効率 V_i が決まっています。

学園祭当日、M 件の仕事が発生しました。各仕事 j (1 \leq j \leq M) には、必要な作業量 D_j と、完了までの制限時間 T_j 時間が指定されています。

高橋君は、各仕事に対してスタッフを1人割り当てるかどうかを決めます。仕事に割り当てられなかったスタッフがいても構いませんし、スタッフが割り当てられず未完了のままとなる仕事があっても構いません。ただし、同じスタッフを複数の仕事に割り当てることはできません。つまり、各スタッフは最大で 1 件の仕事しか担当できません。

スタッフ i が仕事 j を担当する場合、仕事にかかる時間は D_j / V_i 時間です。この仕事を完了できるのは、かかる時間が制限時間以下である場合、すなわち D_j / V_i \leq T_j （V_i \times T_j \geq D_j と同値）を満たす場合に限ります。この条件を満たさないスタッフをその仕事に割り当てることはできません。

高橋君がスタッフの割り当てを最適に行ったとき、完了できる仕事の最大件数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
  • 1 \leq T_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数

入力

N M
V_1 V_2 \ldots V_N
D_1 T_1
D_2 T_2
\vdots
D_M T_M
  • 1 行目には、スタッフの人数を表す N と、仕事の件数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各スタッフの作業効率を表す V_1, V_2, \ldots, V_N が、スペース区切りで与えられる。
  • 3 行目から M 行にわたって、各仕事の情報が与えられる。
  • 2 + j 行目には、j 番目の仕事の必要作業量 D_j と制限時間 T_j が、スペース区切りで与えられる。

出力

完了できる仕事の最大件数を 1 行で出力してください。

入力例 1

3 3
5 3 7
10 2
15 3
6 1

出力例 1

2

入力例 2

4 5
2 4 6 8
12 2
20 5
8 1
24 4
30 3

出力例 2

3

入力例 3

6 7
10 20 15 5 25 30
100 5
50 2
200 10
75 3
150 6
300 15
80 4

出力例 3

3

Score : 400 pts

Problem Statement

Takahashi is serving as the executive committee chairman of a school festival and has hired N part-time staff members. Each staff member i (1 \leq i \leq N) has a work efficiency V_i, which represents the amount of work they can complete per hour.

On the day of the school festival, M jobs have arisen. Each job j (1 \leq j \leq M) has a required workload D_j and a time limit of T_j hours for completion.

Takahashi decides whether to assign a staff member to each job. It is acceptable for some staff members to not be assigned to any job, and it is also acceptable for some jobs to remain incomplete without any staff assigned. However, the same staff member cannot be assigned to multiple jobs. In other words, each staff member can handle at most 1 job.

When staff member i is assigned to job j, the time required for the job is D_j / V_i hours. The job can be completed only if the required time does not exceed the time limit, that is, only if D_j / V_i \leq T_j (equivalently, V_i \times T_j \geq D_j) is satisfied. A staff member who does not satisfy this condition cannot be assigned to that job.

Determine the maximum number of jobs that can be completed when Takahashi optimally assigns the staff.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
  • 1 \leq T_j \leq 10^9 (1 \leq j \leq M)
  • All inputs are integers

Input

N M
V_1 V_2 \ldots V_N
D_1 T_1
D_2 T_2
\vdots
D_M T_M
  • The first line contains N, the number of staff members, and M, the number of jobs, separated by a space.
  • The second line contains the work efficiencies V_1, V_2, \ldots, V_N of each staff member, separated by spaces.
  • The following M lines provide information about each job.
  • The (2 + j)-th line contains the required workload D_j and the time limit T_j of the j-th job, separated by a space.

Output

Output the maximum number of jobs that can be completed, on a single line.

Sample Input 1

3 3
5 3 7
10 2
15 3
6 1

Sample Output 1

2

Sample Input 2

4 5
2 4 6 8
12 2
20 5
8 1
24 4
30 3

Sample Output 2

3

Sample Input 3

6 7
10 20 15 5 25 30
100 5
50 2
200 10
75 3
150 6
300 15
80 4

Sample Output 3

3