Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Hãy tưởng tượng một thời điểm nào đó trong tương lai con người có trạm không gian ở tất cả các hành tinh. Mỗi hành tinh mã hóa bằng một dãy nhị phân có N phần tử. Luôn luôn có một đường bay giữa hai hành tinh khác nhau mà dãy nhị phân biểu diễn hai hành tinh đó khác nhau duy nhất một bít. Khi bay từ một hành tinh này đến hành tinh khác, các tàu không gian phải trả một khoản thuế cho mỗi điểm dừng. Khoản thuế này được tính trên các bít 1 trong biểu diễn của hành tinh điểm dừng đó. Sẽ có một mảng N số nguyên trong đó phần tử thứ I cho biết thuế phải trả nếu bít i bằng 1.

Ví dụ: Nếu hành tinh xuất phát là 110 và hành tinh đích là 011, dãy thuế là 3 1 2 thì cách đi tốn ít chi phí nhất là: 110 -> 010 -> 011 với tổng chi phí là 1+(1+2)=4.

Hãy viết chương trình tính chi phí thuế thấp nhấp có thể để đi từ hành tinh xuất phát đến hành tinh đích cho trước. 

Input

• Mỗi bộ test gồm 2 dòng:
  • Dòng thứ nhất gồm số N (số bít mô tả hành tinh). Tiếp theo sẽ là hai dãy nhị phân có N phần tử mô tả hành tinh nguồn và hành tinh đích (1<=N<=1000).
  • Dòng thứ 2 ghi N số nguyên dương mô tả mảng thuế tương ứng với mỗi vị trí có bít 1. Các giá trị thuế không quá 10⁶.
• Dòng cuối cùng của input ghi số 0

Output

Với mỗi bộ test ghi trên một dòng giá trị thuế tối thiểu tìm được theo khuôn dạng như trong bộ test ví dụ.

Example

Input:
3 110 011
3 1 2
5 00000 11111
1 2 3 4 5
4 1111 1000
100 1 1 1
30 000000000000000000000000000000 111111111111111111111111111111
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
0

Output:
Case 1: 4
Case 2: 35
Case 3: 106
Case 4: 4960