あなたは高校生向けの国際的なコンテストであと一歩のところで金メダルを逃し、帰国後に自分が受験生であることを発見するに至った。しかしあなたは、受験に必要な N 種類の勉強を全くこなしていない。

集中力に定評のあるあなたは、それぞれの勉強を連続した期間に行うことで、残り W 日の受験勉強を乗り切ることにした。

あなたはこの期間中に N 個の模擬試験を受験することにしている。

各模擬試験は開催日と影響力 d が決まっており、開催日前後 d 日未満の模試をあなたは意識している。そして、その日意識している模試の数があなたのやる気の数値となる。

i 種類目の勉強は i 以上のやる気がある時でないとできない。一日にできる勉強の個数には限りはないので、全ての種類の勉強について、連続して勉強できる最大の日数を調べたい。

W 日間中に N 個の模試が行われる。模試には 0 から N-1 までの異なる整数の番号がつけられている。

それぞれの模試 i には開催日 X[i] と 影響度 D[i] が決まっている。日付 t に対して X[i]-D[i] < t < X[i]+D[i] が成り立つ場合に限り、あなたは日付 t のときに模試 i を意識している。

それぞれの日において、あなたの勉強のやる気はその日にあなたが意識している模試の数である。

あなたがやるべき勉強は N 種類ある。勉強には 1 から N までの異なる整数の番号がつけられている。勉強 k を行えるのはあなたのやる気が k 以上の日だけである。

次のパラメータを持つプロシージャ schedule(W, N, X, D) を実装せよ:

• W -- 受験勉強の日数。受験勉強中の各日付は0以上W未満の整数で表される。
• 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 を行える日が 1 日もない場合は answer(k, 0, 0) と呼び出さねばならない。最長の期間が複数ある場合は L が最も小さいものを選ばねばならない。 answer(k, L, R) はどのような k の順番で呼び出しても構わないが、すべての勉強についてちょうど 1 回ずつ呼び出される必要がある。

なお、あなたは 1 日に何種類でも勉強をすることができるのでそれぞれの勉強について独立に考えてよい。すなわち異なる k の値について、answer(k, L, R) 呼び出しの L, R が表す期間は共通部分を持っていてもよい。

W = 10, N = 3,

の場合を考える。schedule は次のようなパラメータで answer を呼び出す必要がある。(この順番に呼び出す必要はない。)