Sau khi ngăn chặn thành công sự tuyệt chủng của loài mèo trong lễ kỷ niệm Ngày Mèo Quốc gia (NCD) hàng năm, chú mèo Ket đã nhận được các khiếu nại về nạn đói từ vương quốc của những chú mèo ăn thịt đồng loại. Do đó, Ket được giao nhiệm vụ vận chuyển thức ăn để ngăn chúng quay lại với tập tính ăn thịt đồng loại.

Vương quốc mèo này có thể được mô hình hóa như một con đường rất dài chạy từ tây sang đông. Có một kho thức ăn ở đầu phía tây của con đường. Có $n$ ngôi nhà mèo nằm ở phía đông của kho thức ăn, được đánh số từ 1 đến $n$. Đảm bảo rằng $n$ là số chẵn. Ngôi nhà đầu tiên nằm cách kho thức ăn $d[1]$ km về phía đông. Với $i \ge 2$, ngôi nhà thứ $i$ nằm cách ngôi nhà thứ $(i - 1)$ là $d[i]$ km về phía đông.

Ket sẽ lái một chiếc xe tải giao hàng để vận chuyển thức ăn đến các ngôi nhà. Xe tải bắt đầu từ kho thức ăn và ban đầu có $x$ đơn vị nhiên liệu. 1 đơn vị nhiên liệu cho phép Ket lái xe 1 km dọc theo con đường.

Ngôi nhà thứ $i$ có $f[i]$ đơn vị nhiên liệu cho xe tải sử dụng. Xe tải có kho chứa nhiên liệu vô hạn và chỉ dừng lại khi hết nhiên liệu. Xe tải không cần quay lại kho thức ăn sau khi rời đi.

Figure 1. Mô hình hóa vương quốc mèo như một con đường với các ngôi nhà

Ngoài ra, Ket có một chiếc đũa phép. Trong một lần vung đũa, chú có thể hoán đổi lượng nhiên liệu được lưu trữ tại ngôi nhà thứ $i$ và ngôi nhà thứ $(n - i + 1)$. Việc hoán đổi này chỉ có thể thực hiện nếu nhiên liệu ở cả hai ngôi nhà vẫn chưa được sử dụng. Hãy giúp Ket tìm chỉ số của ngôi nhà xa nhất $D$ mà chú có thể đến được, bằng cách sử dụng bất kỳ số lần hoán đổi nào. Đồng thời, hãy giúp Ket tìm số lần hoán đổi tối thiểu $S$ cần thiết để đến được ngôi nhà $D$.

Dữ liệu vào

Chương trình của bạn phải đọc từ đầu vào tiêu chuẩn.

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $x$ cách nhau bởi dấu cách.

Dòng thứ hai của dữ liệu vào chứa $n$ số nguyên $d[1], d[2], \dots, d[n]$ cách nhau bởi dấu cách.

Dòng thứ ba của dữ liệu vào chứa $n$ số nguyên $f[1], f[2], \dots, f[n]$ cách nhau bởi dấu cách.

Dữ liệu ra

Chương trình của bạn phải in ra đầu ra tiêu chuẩn.

In ra hai số nguyên cách nhau bởi dấu cách trên một dòng duy nhất. Số nguyên đầu tiên là $D$, chỉ số của ngôi nhà xa nhất mà Ket có thể đến được, theo sau là $S$, số lần hoán đổi tối thiểu cần thiết để đến được ngôi nhà $D$.

Giới hạn

Với tất cả các trường hợp kiểm thử, dữ liệu vào sẽ thỏa mãn các giới hạn sau:

• $2 \le n \le 500\,000$
• $n$ là số chẵn.
• $1 \le d[i] \le 10^9$ với mọi $1 \le i \le n$
• $1 \le f[i] \le 10^9$ với mọi $1 \le i \le n$
• $d[1] \le x \le 10^9$

Chương trình của bạn sẽ được kiểm tra trên các trường hợp dữ liệu thỏa mãn các hạn chế sau:

Ghi chú: Giá trị tuyệt đối của một số $x$, ký hiệu là $|x|$, là số không âm bằng khoảng cách giữa 0 và $x$ trên trục số. Ví dụ, $|5| = 5$ và $|-5| = 5$.

Ví dụ

Dữ liệu vào 1

6 1
1 1 3 1 1 6
1 1 1 4 3 2

Dữ liệu ra 1

5 1

Ghi chú

Có một kho thức ăn với $n = 6$ ngôi nhà ở phía đông. Xe tải của Ket bắt đầu với $x = 1$ đơn vị nhiên liệu và di chuyển đến ngôi nhà 1. Sau đó, chú tiếp nhiên liệu tại ngôi nhà 1 và lái xe đến ngôi nhà 2. Tại thời điểm này, tối ưu nhất là Ket sử dụng đũa phép để hoán đổi lượng nhiên liệu ở ngôi nhà 2 và 5, cho phép chú nạp 3 đơn vị nhiên liệu và đến được ngôi nhà 3. Sau đó, chú có thể nạp 1 đơn vị nhiên liệu trước khi di chuyển đến hai ngôi nhà tiếp theo, nạp 4 và 1 đơn vị (do lần hoán đổi trước đó) nhiên liệu tại các ngôi nhà 4 và 5 tương ứng.

Sau đó, chú sẽ còn lại 4 đơn vị nhiên liệu, khiến chú không thể di chuyển đến ngôi nhà 6 vì nó yêu cầu 6 đơn vị nhiên liệu. Vì Ket hết nhiên liệu trước khi đến ngôi nhà 6, chú chỉ có thể đi đến ngôi nhà 5. Hơn nữa, chú đã phải thực hiện một lần hoán đổi bằng đũa phép. Do đó, $D = 5$ và $S = 1$.

Dữ liệu vào 2

6 5
3 8 3 1 4 1
2 7 1 6 2 7

Dữ liệu ra 2

6 1

Dữ liệu vào 3

6 2
2 24 25 40 5 11
4 12 14 16 20 30

Dữ liệu ra 3

3 2

Dữ liệu vào 4

6 10
3 6 3 7 8 6
4 3 1 7 1 6

Dữ liệu ra 4

5 1