Submit solution

Points: 0.58 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
by winterwolf94
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Du học Mỹ là ước mơ của nhiều học sinh Việt Nam. Có người nói rằng, muốn đi học ở Mỹ thì phải rất giàu, hoặc là rất giỏi. Trung hội đủ cả ~2~ yếu tố này. Vừa là con nhà đại gia và học ở một trường chuyên danh tiếng, cậu đến Mỹ để hiện thực hóa ước mơ trở thành Batman của mình.

Ở Mỹ phương tiện di chuyển phổ biến nhất là xe hơi. Vốn có niềm đam mê ô tô từ nhỏ, Trung tậu cho mình một chiếc BMW cực xịn để chu du khắp Mỹ. Vào một ngày chủ nhật đẹp trời, Trung bắt đầu chuyến du ngoạn của mình trên xế khủng. Từ Atlanta, Trung lái xe đến New York. Dù không biết đường nhưng nhờ hệ thống định vị toàn cầu Google Map (GM), Trung có thể ung dung chạy trên đường cao tốc. GM báo cho Trung biết đường đến New York gồm ~N~ đoạn đường cao tốc liên tiếp, mỗi đoạn đường gồm ~M~ làn đường. Mỗi đoạn có thể là đường thẳng, quẹo vòng cung ~900~ sang trái hoặc sang phải. Không có ~2~ đoạn đường thẳng liên tiếp (vì nếu vậy đã coi là một đoạn: ~D)~.

Mỗi làn đường rộng ~10m~. Ta xem như xe của Trung là một điểm nhỏ trên hình ví dụ. Trung luôn chạy xe ở chính giữa làn đường. Trên các đoạn đường thẳng, Trung có thể điều khiển cho xe chuyển làn. Để chuyển qua một làn đường (về phía bên trái hoặc bên phải làn đường hiện tại) thì đoạn đường đó ít nhất phải dài là ~100m~. Tương tự để chuyển qua ~2~ làn đường thì độ dài đoạn đường ít nhất phải là ~200m~. Trên các đường quẹo Trung không được chuyển làn xe vì làm vậy sẽ vi phạm luật giao thông và phải nộp phạt.

Là một cựu học sinh chuyên Tin, Trung tìm cách đi sao cho độ dài đường đi ngắn nhất (và dĩ nhiên là tiết kiệm xăng nhất ~J)~. Trung sẽ chọn một làn đường để xuất phát và đến New York trên một làn đường bất kì.

Để xem hình minh họa test ví dụ vào ~1~ trong ~2~ link sau

http://www.freeimagehosting.net/639xb

http://upanh.com/drive_pic_upanh/v/avf0bceq3df.htm

Input

  • Dòng đầu gồm ~2~ số ~N~, ~M~ -- số đoạn đường và số làn đường trên mỗi đoạn.

  • Dòng thứ hai gồm ~N~ số nguyên ~L_i~ thể hiện đoạn đường thứ ~i~

    • ~L_i~ ~= 0~: đường thẳng
    • ~L_i~ ~= 1~: quẹo vòng cung ~900~ sang trái
    • ~L_i~ ~= 2~: quẹo vòng cung ~900~ sang phải
  • Dòng cuối cùng gồm ~N~ số nguyên dương ~S_i~. Nếu đoạn đường thứ ~i~ thẳng: ~S_i~ là chiều dài đoạn đường ~i~ quẹo: ~S_i~ là bán kính trong của khúc quẹo ~i~ (xem trên hình)

Output

  • In ra một số thực duy nhất là độ dài quãng đường ngắn nhất Trung sẽ đi. Lấy chính xác đến 2 chữ số thập phân.

Giới hạn

  • ~1 \leq N~, ~S_i~ ~\leq 10000~, ~1 \leq M \leq 20~.
  • Lấy số pi ~=~ ~3.141592654~

Sample Input

3 3
2 0 1
100 1000 100

Sample Output

1330.07

Comments

Please read the guidelines before commenting.


There are no comments at the moment.