Một nhóm n bạn đi tập văn nghệ về khuya. Cả nhóm chỉ
có 1 chiếc đèn pin và phải qua 1 cây cầu gồm m đoạn, các đoạn được đánh số từ 1
đến m kể từ vị trí bờ đang đứng sang bờ kia. Coi vị trí n bạn đang đứng là đoạn
thứ 0 và đầu cầu bên kia là vị trí m+1. Cây cầu đã cũ, do đó có một số đoạn của
cầu đã hỏng và không thể đi vào được, hơn nữa cầu chỉ chịu được sức nặng của
không quá hai người. Để qua cầu an toàn, các bạn phải tổ chức qua cầu theo cách
thức sau: mỗi lượt chỉ có 2 người cầm đèn pin để cùng nhau qua cầu và không
được đi vào những vị trí đoạn cầu bị hỏng. Sau khi hai người qua đến đầu cầu
bên kia thì những người đã qua cầu phải cử 1 người đem đèn pin trở lại đầu cầu
bên này để các bạn khác tiếp tục qua cầu ... Mỗi đơn vị thời gian, bạn thứ i có
thể bước không quá ri đoạn, nghĩa là nếu bạn thứ i đang ở đoạn thứ s của cây cầu
thì bạn có thể di chuyển vào một trong các đoạn thứ s+1, s+2, ..., s+ri nếu đoạn đó không bị hỏng. Việc thực hiện một bước đi đòi
hỏi 1 đơn vị thời gian. Do đó có thể có người qua cầu nhanh hơn, có người qua
cầu chậm hơn. Nếu 2 bạn đi cùng nhau qua cầu thì họ phải di chuyển qua cầu với
thời gian của bạn chậm hơn. Vì đã quá khuya nên cả nhóm bàn nhau tìm cách qua
cầu sớm nhất có thể được.
Yêu cầu:
* Cho biết vị trí các đoạn cầu bị hỏng và khả năng di chuyển của
từng bạn (được mô tả bằng các số r1, r2, ..., rn),
* Hãy tính khoảng thời gian ngắn nhất để n bạn qua được cầu.
Giải thiết rằng luôn có cách để cả nhóm vượt qua cầu.
Ràng buộc: 50% số tests ứng với 50% số điểm của bài có n ≤ 10.
Input
* Dòng thứ nhất chứa hai số nguyên dương n và m tương
ứng là số bạn trong nhóm và số đoạn của cây cầu (n ≤ 10000; m ≤ 100000).
* Dòng thứ hai chứ n số nguyên dương r1, r2, ..., rn (ri ≤ 100, i = 1, 2, ..., n).
* Dòng thứ ba chứa một xâu gồm m ký tự '0' hoặc '1' mô
tả trạng thái của cây cầu. Ký tự thứ i của xâu là '0' nếu đoạn cầu thứ i không
bị hỏng có thể đi vào được, là '1' nếu đoạn cầu thứ i bị hỏng không thể đi vào
được.
* Các số trên cùng một dòng được ghi cách nhau ít nhất
một dấu cách.
Output
* Ghi ra một số nguyên là khoảng thời gian ngắn nhất để
n bạn vượt qua được cây cầu.
Input:
3 5
2 2 4
00100
2 2 4
00100
Output: 8
Solution: CROSS12
Code: CROSS12
