Homework and Series Dilemma

Jill has n homework tasks and m episodes of a series to watch. The i-th homework task takes \(a_i\) minutes to complete and must be finished within \(d_i\) minutes from now. The episodes must be watched in order: the j-th episode lasts \(l_j\) minutes. Jill and her friend will have a call at time \(t_k\) (in minutes from now) to discuss the series, and the discussion does not interrupt homework work.

Jill can interleave her homework tasks and the episodes arbitrarily; however, once started, neither a homework task nor an episode can be interrupted. Your goal is: for each given call time \(t_k\), determine the maximum number of episodes Jill can watch completely before time \(t_k\) while still being able to finish all her homework tasks on time.

Note: It is assumed that the homework tasks alone are feasible, i.e. there exists an ordering in which every task is completed by its deadline.

Observation and Strategy:
If Jill does all episodes first and then starts her homework tasks, the homework tasks will be delayed by the total episodes watching time. When the tasks are scheduled optimally (by processing them in the order of increasing deadlines) the necessary condition for homework feasibility becomes \[ \text{For all } i:\quad \Big(\sum_{j=1}^i a_{(j)}\Big) + E \le d_{(i)}, \] where \(E\) is the total time spent watching episodes and \(a_{(j)}\) and \(d_{(j)}\) are the durations and deadlines after sorting the tasks by deadline. Hence the maximum extra delay that can be inserted without harming the homework schedule is \[ \text{slack} = \min_{1 \le i \le n} \Big(d_{(i)} - \sum_{j=1}^i a_{(j)}\Big). \] To be safe Jill must have the episodes block fit entirely before her call, so we must have \(E \le t_k\) as well. Therefore, for each query time \(t_k\) if we let \[ \text{limit} = \min(\text{slack}, t_k), \] then the maximum number of episodes she can watch is the largest \(x\) (with \(0 \le x \le m\)) such that \[ \sum_{j=1}^{x} l_j \le \text{limit}. \] A simple approach is to precompute the prefix sums of the episodes durations and then, for each query, use binary search to find the maximum \(x\) that satisfies the inequality.

inputFormat

The input begins with three integers \(n\), \(m\), and \(q\) separated by spaces, where \(n\) is the number of homework tasks, \(m\) is the number of episodes, and \(q\) is the number of queries. The following \(n\) lines each contain two integers \(a_i\) and \(d_i\) (the duration and deadline for the \(i\)-th task). The next line contains \(m\) integers \(l_1, l_2, \dots, l_m\) -- the durations of the episodes in order. Finally, the next \(q\) lines each contain one integer \(t_k\), representing a possible call time.

Constraints:

• \(1 \le n, m, q \le 10^5\)
• \(1 \le a_i, d_i, l_j, t_k \le 10^9\)
• The homework tasks are guaranteed to be feasible on their own (i.e. when \(E=0\)).

outputFormat

For each query, output a single integer on a new line: the maximum number of episodes Jill can watch before time \(t_k\) while still being able to complete all homework tasks on time.

sample

3 4 3
3 10
2 8
4 15
2 3 1 5
12
8
20

2
2
2