猫の絶滅を食い止めるという年次行事「National Cat Day (NCD)」の祝賀を無事に終えた猫のKetは、今度は共食いをする猫の王国から空腹の苦情を受け取りました。そこでKetは、彼らが再び共食いに走るのを防ぐために食料を届ける任務を任されました。
この猫の王国は、西から東へ伸びる非常に長い道路としてモデル化できます。道路の西端にはフードバンクがあります。フードバンクの東側には $n$ 個の猫の家があり、1 から $n$ まで番号が振られています。$n$ は偶数であることが保証されています。最初の家はフードバンクから東に $d[1]$ キロメートルの位置にあります。$i \ge 2$ について、$i$ 番目の家は $(i - 1)$ 番目の家から東に $d[i]$ キロメートルの位置にあります。
Figure 1. 猫の王国の道路とフードバンク、各家の配置のモデル図
Ketは配送トラックを運転して各家に食料を届けます。トラックはフードバンクから出発し、最初は $x$ 単位の燃料を持っています。燃料 1 単位で、Ketはトラックを道路に沿って 1 キロメートル走らせることができます。
$i$ 番目の家には、トラックが使用できる $f[i]$ 単位の燃料があります。トラックの燃料タンクの容量は無限であり、燃料が尽きたときにのみ停止します。トラックは出発後にフードバンクへ戻る必要はありません。
さらに、Ketは魔法の杖を持っています。杖を一度振るごとに、$i$ 番目の家と $(n - i + 1)$ 番目の家にある燃料の量を入れ替えることができます。この入れ替えは、両方の家の燃料がまだ使用されていない場合にのみ行うことができます。任意の回数の入れ替えを行ってKetが到達できる最も遠い家の番号 $D$ を求めてください。また、家 $D$ に到達するために必要な最小の入れ替え回数 $S$ も求めてください。
詳細な説明については、入出力例 1 を参照してください。
入力
入力は標準入力から読み込まれます。
1 行目には、2 つの整数 $n$ と $x$ がスペース区切りで与えられます。 2 行目には、$n$ 個の整数 $d[1], d[2], \dots, d[n]$ がスペース区切りで与えられます。 3 行目には、$n$ 個の整数 $f[1], f[2], \dots, f[n]$ がスペース区切りで与えられます。
出力
標準出力に、スペース区切りの 2 つの整数を 1 行で出力してください。最初の整数はKetが到達できる最も遠い家の番号 $D$ であり、2 番目の整数は家 $D$ に到達するために必要な最小の入れ替え回数 $S$ です。
制約
すべてのテストケースにおいて、以下の条件を満たします。
- $2 \le n \le 500\,000$
- $n$ は偶数である。
- $1 \le d[i] \le 10^9$ （すべての $1 \le i \le n$ について）
- $1 \le f[i] \le 10^9$ （すべての $1 \le i \le n$ について）
- $d[1] \le x \le 10^9$
プログラムは、以下の制限を満たす入力に対してテストされます。
| 小課題 | 配点 | 追加の制約 | ||
|---|---|---|---|---|
| 0 | 0 | 入出力例 | ||
| 1 | 7 | すべての $1 \le i \le n$ について $ | f[i] - f[n - i + 1] | = k$ となる定数 $k$ が存在する |
| 2 | 12 | $n \le 40$ | ||
| 3 | 14 | $f$ は非減少である（すべての $1 \le i \le n - 1$ について $f[i] \le f[i + 1]$） | ||
| 4 | 19 | $D \le \frac{n}{2}$ | ||
| 5 | 21 | $n \le 5000$ | ||
| 6 | 27 | 追加の制約なし |
注記
数 $x$ の絶対値は $|x|$ と表記され、数直線上の 0 と $x$ の間の距離に等しい非負の数です。例えば、 $|5| = 5$ および $|-5| = 5$ です。
入出力例
入力 1
6 1 1 1 3 1 1 6 1 1 1 4 3 2
出力 1
5 1
注記 1
フードバンクの東側に $n = 6$ 個の家があります。Ketのトラックは $x = 1$ 単位の燃料で出発し、家 1 へ移動します。その後、家 1 で給油し、家 2 へ移動します。この時点で、Ketが魔法の杖を使って家 2 と家 5 の燃料を入れ替えるのが最適です。これにより 3 単位の燃料を補給でき、家 3 に到達できます。その後、次の 2 つの家へ移動する前に 1 単位の燃料を補給でき、家 4 と家 5 でそれぞれ 4 単位と 1 単位（入れ替えのため）の燃料を補給できます。
この時点で燃料は 4 単位残りますが、家 6 に到達するには 6 単位の燃料が必要なため、移動できません。家 6 に到達する前に燃料が尽きるため、Ketは家 5 までしか移動できません。さらに、魔法の杖で 1 回の入れ替えを行いました。したがって、$D = 5$、$S = 1$ となります。
入力 2
6 5 3 8 3 1 4 1 2 7 1 6 2 7
出力 2
6 1
入力 3
6 2 2 24 25 40 5 11 4 12 14 16 20 30
出力 3
3 2
入力 4
6 10 3 6 3 7 8 6 4 3 1 7 1 6
出力 4
5 1