Problem: You have 4 bags A, B, C and D each of which includes N coins (there are totally 4N coins). Values of the coins in each bag are ai, bi, ci and di respectively.

Find the number of combinations that result when you choose one coin from each bag (totally 4 coins) in such a way that the total value of the coins is V. You should distinguish the coins in a bag.

Constraints

* 1 ≤ N ≤ 1000
* 1 ≤ ai, bi, ci, di ≤ 1016
* 1 ≤ V ≤ 1016
* All input values are given in integers

Input

The input is given in the following format.


N V
a1 a2 ... aN
b1 b2 ... bN
c1 c2 ... cN
d1 d2 ... dN


Output

Print the number of combinations in a line.

Examples

Input

3 14
3 1 2
4 8 2
1 2 3
7 3 2


Output

9


Input

5 4
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1


Output

625

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.Arrays;
import java.util.StringTokenizer;


class Main{
	public static void main(String[] args){
		SC sc=new SC(System.in);
		int N=sc.nextInt();
		long V=sc.nextLong();
		long[] a=new long[N];
		long[] b=new long[N];
		long[] c=new long[N];
		long[] d=new long[N];
		long[] first=new long[N*N];
		long[] sec=new long[N*N];
		for(int i=0; i<N; i++){
			a[i]=sc.nextLong();
		}
		for(int i=0; i<N; i++){
			b[i]=sc.nextLong();
		}
		for(int i=0; i<N; i++){
			c[i]=sc.nextLong();
		}
		for(int i=0; i<N; i++){
			d[i]=sc.nextLong();
		}

		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				first[i*N+j]=a[i]+b[j];
			}
		}
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				sec[i*N+j]=c[i]+d[j];
			}
		}
		Arrays.sort(sec);
		long sum=0;
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				long s=lower_bound(sec,V-first[i*N+j]);
				long t=lower_bound(sec,V-first[i*N+j]+1);
				if(s==-1){
					continue;
				}
				else if(t==-1 && sec[(int)s]==V-first[i*N+j]){
					sum+=(N*N-s);
				}
				else{
					if(sec[(int) s]==V-first[i*N+j]){
						sum+=t-s;
					}
				}
			}
		}
		pl(sum);
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void pl() {
		System.out.println();
	}
	public static void p(Object o) {
		System.out.print(o);
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
		}
	}
	public static final int lower_bound(final long[] arr, final long value) {
		int low = 0;
		int high = arr.length;
		int mid;
		while (low < high) {
			mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
			if (arr[mid] < value) {
				low = mid + 1;
			} else {
				high = mid;
			}
		}
		if(low<arr.length) {
			return low;
		}
		else {
			return -1;
		}
	}
}