Chuyển thang máy (Lift Hopping)

Nguồn: UVa Online Judge

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một tòa nhà có nhiều tầng, được đánh số bằng các số nguyên không âm.

Tòa nhà có $n$ thang máy. Mỗi thang máy có tốc độ riêng và chỉ dừng tại một số tầng nhất định.

Với thang máy thứ $i$, thời gian cần để di chuyển giữa hai tầng kề nhau là $T_i$ giây. Do đó, nếu thang máy thứ $i$ di chuyển trực tiếp từ tầng $x$ đến tầng $y$, thời gian di chuyển là

$$|x-y|\cdot T_i$$

giây.

Bạn đang đứng tại tầng $0$ và muốn đến tầng $k$ trong thời gian ngắn nhất.

Mỗi thang máy chỉ có thể được sử dụng tại các tầng mà nó dừng. Khi đang ở trong một thang máy, bạn có thể đi qua các tầng trung gian mà không cần dừng lại tại đó.

Ví dụ, nếu một thang máy dừng tại các tầng

$$0,5,10,20,$$

thì bạn có thể đi trực tiếp từ tầng $0$ đến tầng $20$. Thang máy có thể đi qua các tầng $1,2,\ldots,19$, nhưng bạn chỉ có thể lên hoặc xuống tại các tầng được liệt kê trong danh sách điểm dừng của nó.

Nếu đang ở một tầng mà cả hai thang máy đều dừng, bạn có thể chuyển từ thang máy hiện tại sang thang máy kia. Mỗi lần chuyển từ một thang máy sang một thang máy khác mất đúng $60$ giây.

Khi bắt đầu tại tầng $0$, bạn có thể lên bất kỳ thang máy nào dừng tại tầng $0$ mà không mất $60$ giây. Chi phí $60$ giây chỉ được tính khi bạn thực sự chuyển từ một thang máy sang một thang máy khác trong quá trình di chuyển.

Bạn không được sử dụng cầu thang bộ.

Để được xem là đã đến tầng $k$, bạn phải xuống tại tầng $k$ từ một thang máy có điểm dừng tại tầng này. Việc một thang máy chỉ đi ngang qua tầng $k$ nhưng không dừng tại đó không được xem là đã đến đích.

Nếu $k=0$, bạn đã đứng tại tầng cần đến ngay từ đầu, vì vậy thời gian cần thiết bằng $0$.

Hãy tìm số giây nhỏ nhất cần thiết để đi từ tầng $0$ đến tầng $k$.

Input

• Dòng đầu chứa hai số nguyên $n$ và $k$:

  • $n$ là số lượng thang máy;
  • $k$ là tầng cần đến.

• Dòng thứ hai chứa $n$ số nguyên

$$T_1,T_2,\ldots,T_n,$$

trong đó $T_i$ là số giây mà thang máy thứ $i$ cần để di chuyển qua một tầng.

• Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa danh sách các tầng mà thang máy thứ $i$ dừng.

Các tầng trên mỗi dòng được liệt kê theo thứ tự tăng dần và cách nhau bởi dấu cách.

Số lượng tầng dừng của mỗi thang máy không được ghi riêng trong Input; số lượng này chính là số số nguyên xuất hiện trên dòng tương ứng.

Ví dụ, dòng

0 5 10 12 14 20 25 30

có nghĩa là thang máy tương ứng dừng tại đúng $8$ tầng:

$$0,5,10,12,14,20,25,30.$$

Một tầng có thể xuất hiện trong danh sách của nhiều thang máy. Khi đó, tầng này có thể được sử dụng làm nơi chuyển thang.

Output

In ra đúng một dòng.

• Nếu có thể đi từ tầng $0$ đến tầng $k$, in ra số giây nhỏ nhất cần thiết.
• Nếu không tồn tại cách di chuyển hợp lệ, in ra:

IMPOSSIBLE

Subtask

Gọi $s_i$ là số tầng dừng của thang máy thứ $i$ và đặt

$$M=\sum_{i=1}^{n}s_i.$$

Như vậy, $M$ là tổng số điểm dừng được liệt kê trong toàn bộ Input.

• Subtask 1 — 15% — Time Limit: 0.50 giây: $n=1$; $0\le k\le10^9$; $1\le T_1\le100$; mọi tầng dừng thuộc $[0,10^9]$; $M\le2\cdot10^5$.
• Subtask 2 — 20% — Time Limit: 1.00 giây: $1\le n\le100$; $0\le k\le99$; $1\le T_i\le100$; mọi tầng dừng thuộc $[0,99]$; $M\le10^4$.
• Subtask 3 — 25% — Time Limit: 1.50 giây: $1\le n\le3000$; $0\le k\le10^9$; $1\le T_i\le100$; mọi tầng dừng thuộc $[0,10^9]$; $M\le3000$.
• Subtask 4 — 40% — Time Limit: 3.00 giây: $1\le n\le2\cdot10^5$; $0\le k\le10^9$; $1\le T_i\le100$; mọi tầng dừng thuộc $[0,10^9]$; $M\le2\cdot10^5$.

Ví dụ

Ví dụ 1

Input

2 30
10 5
0 1 3 5 7 9 11 13 15 20 99
4 13 15 19 20 25 30

Output

275

Giải thích

Có hai thang máy.

Thang máy thứ nhất:

• mất $10$ giây cho mỗi tầng;
• dừng tại các tầng

$$0,1,3,5,7,9,11,13,15,20,99.$$

Thang máy thứ hai:

• mất $5$ giây cho mỗi tầng;
• dừng tại các tầng

$$4,13,15,19,20,25,30.$$

Một cách di chuyển tối ưu là:

1. Lên thang máy thứ nhất tại tầng $0$.
2. Đi từ tầng $0$ đến tầng $13$.
3. Chuyển sang thang máy thứ hai tại tầng $13$.
4. Đi từ tầng $13$ đến tầng $30$.

Thời gian đi từ tầng $0$ đến tầng $13$ bằng thang máy thứ nhất là

$$13\cdot10=130$$

giây.

Tầng $13$ xuất hiện trong danh sách điểm dừng của cả hai thang máy nên có thể chuyển thang tại đây. Việc chuyển thang mất

$$60$$

giây.

Khoảng cách từ tầng $13$ đến tầng $30$ là $17$ tầng, nên thời gian đi bằng thang máy thứ hai là

$$17\cdot5=85$$

giây.

Tổng thời gian:

$$130+60+85=275.$$

Vì vậy đáp án là 275.

Ví dụ 2

Input

2 30
10 1
0 5 10 12 14 20 25 30
2 4 6 8 10 12 14 22 25 28 29

Output

285

Giải thích

Có thể thực hiện hành trình sau:

1. Đi bằng thang máy thứ nhất từ tầng $0$ đến tầng $10$.
2. Chuyển sang thang máy thứ hai tại tầng $10$.
3. Đi bằng thang máy thứ hai từ tầng $10$ đến tầng $25$.
4. Chuyển lại sang thang máy thứ nhất tại tầng $25$.
5. Đi bằng thang máy thứ nhất từ tầng $25$ đến tầng $30$.

Từ tầng $0$ đến tầng $10$ bằng thang máy thứ nhất mất

$$10\cdot10=100$$

giây.

Chuyển thang tại tầng $10$ mất $60$ giây.

Từ tầng $10$ đến tầng $25$ bằng thang máy thứ hai mất

$$15\cdot1=15$$

giây.

Chuyển thang tại tầng $25$ mất thêm $60$ giây.

Cuối cùng, đi từ tầng $25$ đến tầng $30$ bằng thang máy thứ nhất mất

$$5\cdot10=50$$

giây.

Tổng cộng:

$$100+60+15+60+50=285.$$

Vì vậy đáp án là 285.

Ví dụ 3

Input

3 50
10 50 100
0 10 30 40
0 20 30
0 20 50

Output

3920

Giải thích

Một hành trình tối ưu là:

1. đi bằng thang máy thứ nhất từ tầng $0$ đến tầng $30$;
2. chuyển sang thang máy thứ hai tại tầng $30$;
3. đi từ tầng $30$ xuống tầng $20$;
4. chuyển sang thang máy thứ ba tại tầng $20$;
5. đi từ tầng $20$ lên tầng $50$.

Thang máy thứ nhất mất

$$30\cdot10=300$$

giây.

Sau đó chuyển thang tại tầng $30$, mất $60$ giây.

Thang máy thứ hai đi từ tầng $30$ xuống tầng $20$, quãng đường $10$ tầng, mất

$$10\cdot50=500$$

giây.

Tiếp tục chuyển thang tại tầng $20$, mất thêm $60$ giây.

Cuối cùng, thang máy thứ ba đi từ tầng $20$ đến tầng $50$, quãng đường $30$ tầng, mất

$$30\cdot100=3000$$

giây.

Tổng thời gian là

$$300+60+500+60+3000=3920.$$

Do đó đáp án là 3920.

Ví dụ 4

Input

1 1
2
0 2 4 6 8 10

Output

IMPOSSIBLE

Giải thích

Chỉ có một thang máy và nó dừng tại các tầng

$$0,2,4,6,8,10.$$

Tầng cần đến là tầng $1$.

Mặc dù thang máy đi qua tầng $1$ khi di chuyển từ tầng $0$ đến tầng $2$, nó không dừng tại tầng $1$. Vì vậy bạn không thể xuống tại tầng này.

Không có thang máy nào khác và cũng không được sử dụng cầu thang bộ, nên không thể đến tầng $1$.

Do đó kết quả là IMPOSSIBLE.