Trên mặt phẳng tọa độ, một người cần di chuyển từ điểm xuất phát \(A(a_x, a_y)\) đến điểm tập kết \(B(b_x, b_y)\). Giữa \(A\) và \(B\) có \(n\) cột năng lượng. Cột thứ \(i\) nằm tại hoành độ \(x_i\), trải dài liên tục từ tung độ \(y1_i\) đến \(y2_i\) (\(y1_i \le y2_i\)).

Quy tắc di chuyển và thu thập:

• Người này phải lần lượt thu thập năng lượng tại \(n\) cột theo thứ tự đã cho (\(a_x < x_1 < x_2 < \dots < x_n < b_x\)).
• Để thu thập xong cột thứ \(i\), phải di chuyển qua cả hai điểm mút \((x_i, y1_i)\) và \((x_i, y2_i)\). Người đó có thể chọn đi từ dưới lên (\(y1_i\) đến \(y2_i\)) hoặc từ trên xuống (\(y2_i\) đến \(y1_i\)).
• Từ tọa độ \((x, y)\), tốn đúng \(1\) giây để đi sang phải \((x+1, y)\), lên trên \((x, y+1)\) hoặc xuống dưới \((x, y-1)\). Tuyệt đối không được đi lùi sang trái.

Yêu cầu: Tìm thời gian ngắn nhất (tính bằng giây) để đi từ \(A\), thu thập toàn bộ năng lượng tại \(n\) cột, rồi di chuyển đến \(B\).

Input

• Dòng đầu tiên chứa \(5\) số nguyên \(n, a_x, a_y, b_x, b_y\) (\(1 \le n \le 2 \cdot 10^5\); \(1 \le a_x, a_y, b_x, b_y \le 10^9\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(x_i, y1_i, y2_i\) (\(1 \le x_i, y1_i, y2_i \le 10^9; y1_i \le y2_i\)) mô tả hoành độ và vị trí bắt đầu của tung độ \(y1\) và kết thúc của tung độ \(y2\) của cột năng lượng thứ \(i\).

Output

• In ra một số nguyên duy nhất là thời gian tối thiểu.

Example

2 1 3 5 2
3 1 5
4 4 4

13

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 15\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.