#ijpcsilver. [ijpc_silver]銀メダル (Silver Medal)

[ijpc_silver]銀メダル (Silver Medal)

将以下文本翻译成中文,要求显示为markdown格式,不要渲染:

你是高中生的时候参加了一次国际比赛,差一点就获得金牌。回国后你发现自己是一个应试考生,然而你并没有准备好必考的 **N** 种科目。

因为你集中注意力的能力很强,所以你决定在剩下的 **W** 天里完成所有的考试复习。

你计划在这段时间内参加 **N** 次模拟考试。

每次模拟考试都有一个举办日期和一个影响力 **d**,你会意识到开考前后 **d** 天之内的模拟考试。那么你的动力值就等于你意识到的模拟考试的数量。

第 **i** 种科目只有当你的动力值大于等于 **i** 时才能学习。每天你可以学习任意多的科目,所以你想知道对于所有科目,连续学习的最长天数是多少。

任务
--

已知 **W** 天内有 **N** 次模拟考试。每次模拟考试都标有从 **0** 到 **N-1** 的不同整数编号。

每次模拟考试 **i** 都有一个举办日期 **X\[i\]** 和一个影响度 **D\[i\]**。只有当满足条件 **X\[i\]-D\[i\] < t < X\[i\]+D\[i\]** 时,你才会意识到日期 **t** 时的模拟考试 **i**。

每天,你的学习动力值等于你意识到的模拟考试的数量。

你要准备 **N** 种科目的考试。科目从 **1** 到 **N** 编号。你只能在你的学习动力值大于等于 **k** 的时间学习第 **k** 种科目。

请实现函数 **schedule(W, N, X, D)**:

*   **W** -- 考试复习的天数。考试期间的每一天用一个介于 **0** 到 **W-1** 的整数表示。
*   **N** -- 模拟考试和科目的数量。模拟考试使用从 **0** 到 **N-1** 的不同整数编号,科目使用从 **1** 到 **N** 的不同整数编号。
*   **X** -- 模拟考试的举办日期,使用整数数组表示。假设对于 **0 ≦ i < N**,**0 ≦ X\[i\] < W**。
*   **D** -- 模拟考试的影响度,使用整数数组表示。假设对于 **0 ≦ i < N**,**1 ≦ D\[i\] ≦ W**。可能存在 **X\[i\]-D\[i\] < 0** 或 **X\[i\]+D\[i\] ≧ W** 的情况。

对于每个科目 **k**,请计算你可以连续学习第 **k** 种科目的最长时间,并调用函数 **answer(k, L, R)**。其中 **L**, **R** 表示你可以连续学习第 **k** 种科目的最长时间段的开始和结束日期。如果你无法学习第 **k** 种科目,则需要调用 **answer(k, 0, 0)**。如果存在多个最长时间段,则选择最小的 **L**。函数 **answer(k, L, R)** 在任何顺序下都可以调用,但是必须对每个科目调用一次。

注意,你可以每天学习任意多的科目,所以可以独立地考虑不同的 **k**。也就是说,对于不同的 **k** 值,可以共享相同的学习时间段。

例子
-

**W = 10**, **N = 3**,

**X =**

**4**

**8**

**3**

**D =**

**2**

**4**

**1**

考虑以下情况。在这种情况下,你需要用以下参数调用 **answer** 函数。(不必按照这个顺序调用。)

**参数**

**answer(1, 3, 9)**

**answer(2, 3, 3)**

**answer(3, 0, 0)**

子任务
---

### 子任务 1 (10 分)

*   **1 ≦ W ≦ 50**
*   **1 ≦ N ≦ 50**

### 子任务 2 (19 分)

*   **1 ≦ W ≦ 1 000**
*   **1 ≦ N ≦ 1 000**

### 子任务 3 (71 分)

*   **1 ≦ W ≦ 1 000 000 000**
*   **1 ≦ N ≦ 100 000**

实现细节
-----

### 限制

*   CPU 时间限制: 1 秒
*   内存限制: 64 MB  
    **注意:** 没有限制在栈大小方面。使用作为堆栈的内存将包含在总内存使用量中。

### 接口 (API)

*   实现目录: silver/ (原型: [silver.zip](http://imoz.jp/data/ijpc/silver.zip))
*   参赛者需要编写的文件: silver.cpp 或 silver.h
*   需要提交的文件接口: silver.h
*   评分程序的样例: grader.cpp
*   评分程序的输入样例: grader.in.1, grader.in.2, ...  
    **注意:** 评分程序的样例会读取以下格式的输入。
    *   第一行: 空格分隔的 **W**, **N**。
    *   第二行到第 **N+1** 行: 对于 **0 ≦ i < N**,第 **i+2** 行包含空格分隔的 **X\[i\]** 和 **D\[i\]**。
*   评分程序的输入样例所应产生的输出: grader.expect.1, grader.expect.2, ...  
    **注意:** 评分程序的样例会写入以下格式的输出。
    *   第一行到第 **N** 行: 对于 **1 ≦ k ≦ N**,第 **k** 行包含以空格分隔的最长学习期间的开始和结束日期 **L**, **R**。