Ghép dây

Có \(N\) sợi dây loại \(A\) có độ dài lần lượt là \(a_1, a_2, \ldots, a_N\); \(N\) sợi dây loại \(B\) có độ dài lần lượt là \(b_1, b_2, \ldots, b_N\); \(N\) sợi dây loại \(C\) có độ dài lần lượt là \(c_1, c_2, \ldots, c_N\); \(N\) sợi dây loại \(D\) có độ dài lần lượt là \(d_1, d_2, \ldots, d_N\).

Yêu cầu: Hãy đếm số cách chọn đúng \(1\) sợi dây loại \(A\), \(1\) sợi dây loại \(B\), \(1\) sợi dây loại \(C\) và \(1\) sợi dây loại \(D\) sao cho tổng độ dài bằng \(L\). Hai cách chọn khác nhau nếu có ít nhất một loại dây mà chỉ số sợi dây được chọn khác nhau.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(N\) và \(L\) (\(1 \le N \le 1000\); \(1 \le L \le 10^9\)).

• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le 10^9\)) lần lượt là độ dài của \(N\) sợi dây loại \(A\).

• Dòng thứ ba chứa \(N\) số nguyên dương \(b_1, b_2, \ldots, b_N\) (\(1 \le b_i \le 10^9\)) lần lượt là độ dài của \(N\) sợi dây loại \(B\).

• Dòng thứ tư chứa \(N\) số nguyên dương \(c_1, c_2, \ldots, c_N\) (\(1 \le c_i \le 10^9\)) lần lượt là độ dài của \(N\) sợi dây loại \(C\).

• Dòng thứ năm chứa \(N\) số nguyên dương \(d_1, d_2, \ldots, d_N\) (\(1 \le d_i \le 10^9\)) lần lượt là độ dài của \(N\) sợi dây loại \(D\).
  Các số ghi trên cùng một dòng được ghi cách nhau một dấu cách.

Ràng buộc:

• Có \(40\%\) số test tương ứng với \(40\%\) số điểm: \(N \le 50\).

• Có \(60\%\) số test tương ứng với \(60\%\) số điểm: không có ràng buộc gì thêm.

Output

Dòng thứ nhất ghi một số nguyên \(t\) là kết quả tìm được.

Example

Input:

3 28
1 1 1
1 1 1
10 11 12
13 14 15

Output:

18

Note

Tổng của hai sợi dây loại \(A\) và \(B\) luôn bằng \(2\), nên cần chọn hai sợi loại \(C\) và \(D\) có tổng \(26\): có hai cặp giá trị \((11, 15)\) và \((12, 14)\). Mỗi cặp giá trị ứng với đúng một cặp chỉ số, còn loại \(A\), \(B\) có \(3 \times 3 = 9\) cách chọn, tổng cộng \(2 \times 9 = 18\) cách.