(uav.*)

Một cuộc đua dành cho máy bay không người lái thông minh (UAV cỡ nhỏ) được tổ chức trên một đường băng dài gồm N vạch cách đều nhau, vách cách vạch 10 mét. Các vạch được đánh số từ 1 đến N. Trên mỗi vạch đều có đặt một bộ cảm biến có nhiệm vụ gửi về trung tâm điều khiển (TTDK) của Ban tổ chức (BTC) cuộc thi số hiệu của vạch khi UAV đứng hay hạ cánh tại vạch này. Cuộc đua cho mỗi UAV được tiến hành như sau: UAV vào đứng tại vạch 1, có thời gian 1 giây để nạp dữ liệu mà BTC cung cấp, dữ liệu gồm một số nguyên dương L và N số nguyên X_i (i=1..n) với ý nghĩa X_i là giá trị của vạch i. Ngay sau đó, UAV phải được thực hiện hành trình bằng cách di chuyển liên tục như sau:

+ Trong hành trình lượt đi, UAV (đứng tại vạch 1) cần bay đến vạch N theo quy tắc: Nếu đang đứng ở vạch i (1≤i<N) thì nó sẽ chỉ được phép hạ cánh tại vạch j (j>i) mà X_j lẻ (ấn định rằng X_N=1001) đồng thời vạch j cách vạch i không quá L vạch (tức là 1≤j-i≤L). Tổng số lần UAV đứng hay hạ cánh trong hành trình lượt đi, bao gồm tại cả vạch 1 và vạch N, được ký hiệu bởi U.

+ Trong hành trình lượt về, bắt đầu với số điểm được BTC cung cấp bằng X_n=1001, UAV từ vạch N bay tiếp về vạch 1 theo quy tắc: Nếu đang đứng ở vạch i (1<i≤n) thì nó sẽ chỉ được phép hạ cánh tại vạch k (k<i) mà X_K chẵn (ấn định rằng X₁=1000). UAV sẽ nhận được thêm X_k điểm nếu vạch k cách vạch i đúng L vạch (tức i-k=L) và bị trừ X_k điểm trong trường hợp trái lại. Tổng số điểm mà UAV thu được trong hành trình lượt về, được ký hiệu là V.

Lưu ý:

+ Các UAV được lập trình sẵn để tiếp nhận và xử lý dữ liệu của BTC rồi tự động thực hiện toàn bộ hành trình (lượt đi và về).

+ Dữ liệu mà BTC đưa ra luôn đảm bảo để các UAV có thể thực hiện được cuộc đua.

Yêu cầu: Hãy lập trình cho UAV để nó đạt được giá trị nhỏ nhất của U và lớn nhất của V.

Dữ liệu vào:

+ Dòng đầu ghi số nguyên L (10≤L≤100).

+ Dòng thứ 2 ghi số nguyên N (L<N≤500000).

+ Dòng thứ 3 ghi lần lượt các số nguyên X₂, X₃,…,X_n-1 (0≤X_i≤10⁶, i=2,…,N-1)

Các số trên một dòng cách nhau bởi ít nhất một dấu cách.

Kết quả: Ghi 2 số nguyên trên 2 dòng: Dòng đầu là U và dòng sau là V.

Ví dụ:

Ràng buộc: 50% số test ứng với 50% số điểm của bài có N≤1000