Đường sắt IOI có một tuyến đường thẳng gồm \(N + 2\) nhà ga. Các ga trên tuyến được đánh số lần lượt từ \(0\) đến \(N + 1\), bắt đầu từ một đầu tuyến.

Trên tuyến có hai loại tàu: tàu chiều tăng và tàu chiều giảm. Tàu chiều tăng di chuyển theo hướng số hiệu ga tăng dần; tàu chiều giảm di chuyển theo hướng số hiệu ga giảm dần. Đi tàu từ một ga sang ga liền kề mất \(T\) giây. Cụ thể, khi đi tàu chiều tăng, ta có thể đi từ ga \(i\) đến ga \(i + 1\) trong \(T\) giây; khi đi tàu chiều giảm, ta có thể đi từ ga \(i\) đến ga \(i - 1\) trong \(T\) giây. Tuy nhiên, không thể lên tàu chiều tăng tại ga \(N + 1\) hoặc lên tàu chiều giảm tại ga \(0\). Tàu đến rất thường xuyên, nên có thể bỏ qua thời gian chờ tàu.

Mỗi ga có một sân ga dành cho tàu chiều tăng và một sân ga dành cho tàu chiều giảm. Trên lối đi nối hai sân ga có đặt một bàn đóng dấu.

Hiện tại, đường sắt IOI đang tổ chức một hoạt động sưu tập dấu. Để hoàn thành hoạt động này, người tham gia phải xuất phát từ sân ga tàu chiều tăng của ga \(0\), lấy một dấu tại mỗi ga từ \(1\) đến \(N\), rồi đến sân ga tàu chiều tăng của ga \(N + 1\).

Để lấy dấu tại một ga, người tham gia phải xuống tàu rồi đi bộ đến bàn đóng dấu nằm trên lối đi của ga. Thời gian di chuyển giữa sân ga tàu chiều tăng, bàn đóng dấu và sân ga tàu chiều giảm tại ga \(i\) được cho như sau:

• Từ sân ga tàu chiều tăng của ga \(i\) đến bàn đóng dấu: \(U_i\) giây.
• Từ bàn đóng dấu đến sân ga tàu chiều tăng của ga \(i\): \(V_i\) giây.
• Từ sân ga tàu chiều giảm của ga \(i\) đến bàn đóng dấu: \(D_i\) giây.
• Từ bàn đóng dấu đến sân ga tàu chiều giảm của ga \(i\): \(E_i\) giây.

Người tham gia chỉ được ghé ga \(0\) và ga \(N + 1\) mỗi ga một lần. Tại các ga từ \(1\) đến \(N\), người tham gia có thể xuống tàu bao nhiêu lần tùy ý.

Cấu trúc ga \(i\).

Yêu cầu

Cho số ga có dấu cần sưu tập, thời gian đi tàu giữa hai ga liền kề, thời gian di chuyển giữa sân ga tàu chiều tăng và bàn đóng dấu tại mỗi ga, cùng thời gian di chuyển giữa sân ga tàu chiều giảm và bàn đóng dấu tại mỗi ga. Hãy viết chương trình tìm thời gian ít nhất để hoàn thành hoạt động sưu tập dấu.

Thời gian hoàn thành được tính từ lúc xuất phát tại ga \(0\), lấy đủ \(N\) dấu, cho đến khi đến sân ga tàu chiều tăng của ga \(N + 1\). Có thể bỏ qua thời gian chờ tàu ở sân ga và thời gian đóng dấu.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(N, T\), cách nhau bởi dấu cách. Tuyến đường có \(N + 2\) ga và thời gian đi tàu giữa hai ga liền kề là \(T\) giây.
• \(N\) dòng tiếp theo mô tả thời gian di chuyển tại các ga. Dòng thứ \(i\) trong số này (\(1 \le i \le N\)) chứa bốn số nguyên \(U_i, V_i, D_i, E_i\), cách nhau bởi dấu cách, với ý nghĩa như sau:

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là thời gian ít nhất, tính bằng giây, để hoàn thành hoạt động sưu tập dấu.

Ràng buộc

Tất cả dữ liệu đầu vào thỏa mãn:

• \(1 \le N \le 3\,000\).
• \(1 \le T \le 100\,000\).
• \(1 \le U_i \le 100\,000 \quad (1 \le i \le N)\).
• \(1 \le V_i \le 100\,000 \quad (1 \le i \le N)\).
• \(1 \le D_i \le 100\,000 \quad (1 \le i \le N)\).
• \(1 \le E_i \le 100\,000 \quad (1 \le i \le N)\).

Phân nhóm

• Nhóm 1 (10 điểm): \(N \le 16\)
• Nhóm 2 (75 điểm): \(N \le 100\)
• Nhóm 3 (15 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 1
1 1 1 1
1 9 9 1
9 9 1 1
1 9 9 1

23

6 2
5 5 3 5
9 7 9 3
3 4 9 4
8 2 6 6
8 5 7 5
3 2 1 6

73