Bedao Regular Contest 07 - TRAIN

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

~Neko~ rất thích mua sắm, thành phố ~Neko~ đang sống có ~1~ chuỗi ~n~ cửa hàng. Chuỗi cửa hàng có thể mô tả bằng một dãy số, mỗi cửa hàng có tọa độ ~x_1~, ~x_2~, ... ~x_N~. Trên chuỗi có ~N + 2~ ga tàu lửa, mỗi cửa hàng đều có một ga tàu lửa, ngoài ra còn một ga nằm ở tọa độ ~0~ và một trạm nằm ở tọa độ ~L~.

Ở thời gian ~0~, tàu khởi hành từ ga ~0~ theo chiều dương. Đoàn tàu đi với vận tốc ~1~ đơn vị/giây. Tại thời điểm ~L~, tàu sẽ đến ga cuối cùng ở tọa độ ~L~. Khi đó tàu sẽ ngay lập tức quay đầu đi ngược chiều với cùng vận tốc theo chiều âm. Tại thời điểm ~2L~, đoàn tàu sẽ đến ga ~0~ và ngay lập tức lại quay ngược lại theo chiều dương. Quá trình này lặp lại vô hạn.

Khi tàu đến ga có ~Neko~, ~Neko~ có thể lên (nếu không ở trên tàu) hoặc rời tàu (nếu ở trên tàu) ngay lập tức. Tại thời điểm ~0~, Neko đang ở nhà ga ~0~.

~Neko~ muốn đi mua sắm ở tất cả ~N~ cửa hàng (đi theo thứ tự lần lượt từ ~1~ đến ~N~). ~Neko~ tốn ~t_i~ giây để mua sắm trong cửa hàng có tọa độ ~x_i~ trước khi chuyển sang cửa hàng tiếp theo. Để chuyển sang cửa hàng tiếp theo thì tất nhiên ~Neko~ phải bắt xe lửa. ~Neko~ có thể lên tàu ngay lập tức sau khi mua sắm xong (nếu vị trí của tàu trùng với tọa độ ga ~Neko~ đang đứng) hoặc phải chờ cho đến khi tàu đến.

Hãy tìm thời gian tối thiểu để ~Neko~ hoàn thành việc mua sắm của mình và trở về nhà tại ga ~0~.

Input

  • Dòng đầu chứa ~2~ số nguyên ~N~ và ~L~ cách nhau bởi ~1~ dấu cách. ~(1 \le N \le 300000, 1 \le L \le 10^9)~
  • Dòng tiếp theo chứa dãy số ~x_1~, ~x_2, \dots ,x_N~, dữ liệu đảm bảo tọa độ của các cửa hàng phân biệt. ~(0 < x_i < L)~
  • Dòng cuối cùng chứa dãy số ~t_1~, ~t_2, \dots ,t_N~ ~(1 \le t_i \le 10^9)~

Output

  • Ghi ra thời gian tối thiếu (tính bằng giây) để ~Neko~ hoàn tất việc mua sắm của mình và trở về nhà tại ga ~0~.

Sample Input

2 10 
5 8 
10 4

Sample Output

40

Subtask

  • ~30\%~ số test có ~N \le 100, L \le 1000, t_i \le 1000~
  • ~70\%~ số test còn lại không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.