Giải bài trực tuyến

            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 90⁰ 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 90⁰ sang trái
• L_i = 2 : quẹo vòng cung 90⁰ 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)

          Giới hạn :     1 <= N, S_i <= 10000,       1 <= M <= 20.

                            Lấy số pi = 3.141592654

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.

Example

Input:
3 3
2 0 1
100 1000 100

Output:
1330.07