Sau một ngày đi chơi siêu cháy ở lễ hội cosplay Nubustes, shiba và _minhduc phải trở về nhà của mình để còn tiếp tục làm việc và viết đề, sinh test cho các LQDOJ-er :Đ

Giữa hai tỉnh có tất cả \(n\) địa điểm và có \(m\) con đường nối các điểm này với nhau. Hiện tại, lễ hội Nubustes đang diễn ra tại điểm \(1\), _minhduc và shiba cần phải về tới nhà tại điểm \(n\). Các con đường này đều là đường hai chiều, con đường thứ \(i\) nối hai địa điểm \(u_{i}\) và \(v_{i}\) với nhau. Có hai cách đi trong một con đường:

• Đi bằng xe máy của hai người và tốn chi phí bằng một lượng \(c_{i}\) đồng.
• Dắt xe máy lên một chiếc xe buýt và phải trả cho tài xế chi phí bằng một lượng \(d_{i}\) đồng.

Tuy nhiên, mỗi lần đổi giữa đi xe máy và đi xe buýt, hai người đều mất chi phí bằng \(1\). Ví của hai người có thể chứa tối đa \(k\) đồng. Ban đầu, tại lễ hội Nubustes họ đã có đầy ví tiền. Ngoài ra, ở mỗi điểm đều có ngân hàng, ngân hàng cho phép rút một số tiền bất kì, tuy nhiên cứ với mỗi \(100\) đồng bạn rút bạn phải trả chi phí là \(1\) đồng cho ngân hàng, ngoài ra nếu bạn rút một phần tiền chưa đạt đên \(100\) đồng bạn vẫn sẽ mất \(1\) đồng, ví dụ: bạn rút \(500\) đồng bạn phải trả cho ngân hàng phí là \(5\) đồng, bạn rút \(501\) đồng bạn phải trả cho ngân hàng phí là \(6\) đồng.

Hỏi chi phí ít nhất để hai người có thể về tới nhà là bao nhiêu?

Input

• Dòng thứ nhất chứa ba số nguyên dương \(n,m\) (\(n \le 10^4\), \(m \le 10^5\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên biểu diễn một con đường (\(1 \le u,v \le n, 0 \le c,d \le 10^3\)).
• Dòng cuối cùng chứa số nguyên dương \(k\) (\(k \le 10^3\)).
• Dữ liệu đảm bảo con đường nào cũng có thể đi được nếu ví tiền của hai người đầy.

Output

• Một dòng chứa một số nguyên duy nhất là chi phí để di chuyển từ lễ hội Nubustes về đến nhà của _minhduc và shiba.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(d_{i} = 1000\) với \(i = 1,2,3...,m\).
• Subtask \(2\) (\(70\%\) số điểm): không có ràng buộc gì thêm.

Example

3 2
1 2 1 99
2 3 99 1
1000

3