Country of Metropolia is holding Olympiad of Metrpolises soon. It mean that all jury members of the olympiad should meet together in Metropolis (the capital of the country) for the problem preparation process.

There are n + 1 cities consecutively numbered from 0 to n. City 0 is Metropolis that is the meeting point for all jury members. For each city from 1 to n there is exactly one jury member living there. Olympiad preparation is a long and demanding process that requires k days of work. For all of these k days each of the n jury members should be present in Metropolis to be able to work on problems.

You know the flight schedule in the country (jury members consider themselves important enough to only use flights for transportation). All flights in Metropolia are either going to Metropolis or out of Metropolis. There are no night flights in Metropolia, or in the other words, plane always takes off at the same day it arrives. On his arrival day and departure day jury member is not able to discuss the olympiad. All flights in Megapolia depart and arrive at the same day.

Gather everybody for k days in the capital is a hard objective, doing that while spending the minimum possible money is even harder. Nevertheless, your task is to arrange the cheapest way to bring all of the jury members to Metrpolis, so that they can work together for k days and then send them back to their home cities. Cost of the arrangement is defined as a total cost of tickets for all used flights. It is allowed for jury member to stay in Metropolis for more than k days.

Input

The first line of input contains three integers n, m and k (1 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ k ≤ 106). 

The i-th of the following m lines contains the description of the i-th flight defined by four integers di, fi, ti and ci (1 ≤ di ≤ 106, 0 ≤ fi ≤ n, 0 ≤ ti ≤ n, 1 ≤ ci ≤ 106, exactly one of fi and ti equals zero), the day of departure (and arrival), the departure city, the arrival city and the ticket cost.

Output

Output the only integer that is the minimum cost of gathering all jury members in city 0 for k days and then sending them back to their home cities.

If it is impossible to gather everybody in Metropolis for k days and then send them back to their home cities, output "-1" (without the quotes).

Examples

Input

2 6 5
1 1 0 5000
3 2 0 5500
2 2 0 6000
15 0 2 9000
9 0 1 7000
8 0 2 6500


Output

24500


Input

2 4 5
1 2 0 5000
2 1 0 4500
2 1 0 3000
8 0 1 6000


Output

-1

Note

The optimal way to gather everybody in Metropolis in the first sample test is to use flights that take place on days 1, 2, 8 and 9. The only alternative option is to send jury member from second city back home on day 15, that would cost 2500 more.

In the second sample it is impossible to send jury member from city 2 back home from Metropolis.
import java.util.*;
import java.text.*;

import javax.swing.plaf.basic.BasicScrollPaneUI.HSBChangeListener;

import java.io.*;
import java.math.*;
public class code5 {
	InputStream is;
	PrintWriter out;
	static long mod=pow(10,9)+7;
	static int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
	void solve() throws Exception
	{
		int n=ni();
		int m=ni();
		int k=ni();
		int size=1000000;
		ArrayList<Pair> alarrive[]=new ArrayList[size+1];
		ArrayList<Pair> aldep[]=new ArrayList[size+1];
		for(int i=0;i<=size;i++)
		{
			alarrive[i]=new ArrayList<Pair>();
			aldep[i]=new ArrayList<Pair>();
		}
		for(int i=0;i<m;i++)
		{
			int d=ni();
			int f=ni();
			int t=ni();
			int c=ni();
			if(f==0)
				aldep[d].add(new Pair(t,c));
			else
				alarrive[d].add(new Pair(f,c));
		}
		long prefix[]=new long[size+1];
		Arrays.fill(prefix,Long.MAX_VALUE);
		long suffix[]=new long[size+2];
		Arrays.fill(suffix,Long.MAX_VALUE);
		long sta[]=new long[n+1];
		Arrays.fill(sta,-1);
		long std[]=new long[n+1];
		int c1=0,c2=0;
		Arrays.fill(std,-1);
		long p1=0,p2=0;
		for(int i=1;i<=size;i++)
		{
			for(int j=0;j<alarrive[i].size();j++)
			{
				if(sta[alarrive[i].get(j).x]==-1)
				{
					c1++;
					p1+=alarrive[i].get(j).y;
					sta[alarrive[i].get(j).x]=alarrive[i].get(j).y;
					
				}else if(sta[alarrive[i].get(j).x]==-1||sta[alarrive[i].get(j).x]>alarrive[i].get(j).y){
				
					p1-=sta[alarrive[i].get(j).x];
					sta[alarrive[i].get(j).x]=alarrive[i].get(j).y;
					p1+=alarrive[i].get(j).y;
				}
			}
			if(c1==n) 
			{
				prefix[i]=Math.min(prefix[i-1],p1);
			}
		}
		for(int i=size;i>=1;i--)
		{
			for(int j=0;j<aldep[i].size();j++)
			{
				if(std[aldep[i].get(j).x]==-1)
				{
					c2++;
					p2+=aldep[i].get(j).y;
					std[aldep[i].get(j).x]=aldep[i].get(j).y;
				}else if(std[aldep[i].get(j).x]>aldep[i].get(j).y)
				{
				
					p2-=std[aldep[i].get(j).x];
					std[aldep[i].get(j).x]=aldep[i].get(j).y;
					p2+=aldep[i].get(j).y;
				}
			}
			
			if(c2==n) 
			{
				suffix[i]=Math.min(suffix[i+1],p2);
			}
		}
		long ans=Long.MAX_VALUE;
		for(int i=1;i+k<=size;i++)
		{
			
			long q1=prefix[i-1];
			long q2=suffix[i+k];
			if(q1==Long.MAX_VALUE||q2==Long.MAX_VALUE)
				continue;
			ans=Math.min(q1+q2,ans);
		}
		out.println(ans==Long.MAX_VALUE?-1:ans);
	}

	public static int count(int x)
	{
		int num=0;
		while(x!=0)
		{
			x=x&(x-1);
			num++;
		}
		return num;
	}
	static long d, x, y;
	void extendedEuclid(long A, long B) {
	    if(B == 0) {
	        d = A;
	        x = 1;
	        y = 0;
	    }
	    else {
	        extendedEuclid(B, A%B);
	        long temp = x;
	        x = y;
	        y = temp - (A/B)*y;
	    }
	}
	long modInverse(long A,long M) //A and M are coprime
	{
	    extendedEuclid(A,M);
	    return (x%M+M)%M;    //x may be negative
	}
	public static void mergeSort(int[] arr, int l ,int r){
		if((r-l)>=1){
			int mid = (l+r)/2;
			mergeSort(arr,l,mid);
			mergeSort(arr,mid+1,r);
			merge(arr,l,r,mid);
		}
	}
	public static void merge(int arr[], int l, int r, int mid){
		int n1 = (mid-l+1), n2 = (r-mid);
		int left[] = new int[n1];
		int right[] = new int[n2];
		for(int i =0 ;i<n1;i++) left[i] = arr[l+i];
		for(int i =0 ;i<n2;i++) right[i] = arr[mid+1+i];
		int i =0, j =0, k = l;
		while(i<n1 && j<n2){
			if(left[i]>right[j]){
				arr[k++] = right[j++];
			}
			else{
				arr[k++] = left[i++];
			}
		}
		while(i<n1) arr[k++] = left[i++];
		while(j<n2) arr[k++] = right[j++];
	}
	public static void mergeSort(long[] arr, int l ,int r){
		if((r-l)>=1){
			int mid = (l+r)/2;
			mergeSort(arr,l,mid);
			mergeSort(arr,mid+1,r);
			merge(arr,l,r,mid);
		}
	}
	public static void merge(long arr[], int l, int r, int mid){
		int n1 = (mid-l+1), n2 = (r-mid);
		long left[] = new long[n1];
		long right[] = new long[n2];
		for(int i =0 ;i<n1;i++) left[i] = arr[l+i];
		for(int i =0 ;i<n2;i++) right[i] = arr[mid+1+i];
		int i =0, j =0, k = l;
		while(i<n1 && j<n2){
			if(left[i]>right[j]){
				arr[k++] = right[j++];
			}
			else{
				arr[k++] = left[i++];
			}
		}
		while(i<n1) arr[k++] = left[i++];
		while(j<n2) arr[k++] = right[j++];
	}
	 static class Pair implements Comparable<Pair>{
		 
	       int x,y,k;
	       int i,dir;
	       long cost;
		Pair (int x,int y){
			this.x=x;
			this.y=y;
		}   
		public int compareTo(Pair o) {
			if(o.x!=this.x)
				return o.x-this.x;
			else
				return this.y-o.y;
		}
	 
		public String toString(){
			return x+" "+y+" "+k+" "+i;}
		public boolean equals(Object o) {
			if (o instanceof Pair) {
				Pair p = (Pair)o;
				return p.x == x && p.y == y ;
			}
			return false;
		}
		public int hashCode() {
			return new Long(x).hashCode()*31 + new Long(y).hashCode();
		}
	} 
	    
	    public static boolean isPal(String s){
	        for(int i=0, j=s.length()-1;i<=j;i++,j--){
	                if(s.charAt(i)!=s.charAt(j)) return false;
	        }
	        return true;
	    }
	    public static String rev(String s){
			StringBuilder sb=new StringBuilder(s);
			sb.reverse();
			return sb.toString();
	    }
	    
	    public static long gcd(long x,long y){
		if(y==0)
			return x;
		else
			return gcd(y,x%y);
	    }
	    
	    public static int gcd(int x,int y){
	    	if(y==0) 
	    		return x; 
	    	return gcd(y,x%y);
	    }
	    
	    public static long gcdExtended(long a,long b,long[] x){
	        
	        if(a==0){
	            x[0]=0;
	            x[1]=1;
	            return b;
	        }
	        long[] y=new long[2];
	        long gcd=gcdExtended(b%a, a, y);
	        
	        x[0]=y[1]-(b/a)*y[0];
	        x[1]=y[0];
	        
	        return gcd;
	    }
	    
	    public static int abs(int a,int b){
		return (int)Math.abs(a-b);
	    }
	 
	    public static long abs(long a,long b){
		return (long)Math.abs(a-b);
	    }
	    
	    public static int max(int a,int b){
		if(a>b)
			return a;
		else
			return b;
	    }
	 
	    public static int min(int a,int b){
		if(a>b)
			return b;
		else 
			return a;
	    }
	    
	    public static long max(long a,long b){
		if(a>b)
			return a;
		else
			return b;
	    }
	 
	    public static long min(long a,long b){
		if(a>b)
			return b;
		else 
			return a;
	    }
	 
	    public static long pow(long n,long p,long m){
		 long  result = 1;
		  if(p==0)
		    return 1;
		if (p==1)
		    return n;
		while(p!=0)
		{
		    if(p%2==1)
		        result *= n;
		    if(result>=m)
		    result%=m;
		    p >>=1;
		    n*=n;
		    if(n>=m)
		    n%=m;
		}
		return result;
	    }
	    
	    public static long pow(long n,long p){
		long  result = 1;
		  if(p==0)
		    return 1;
		if (p==1)
		    return n;
		while(p!=0)
		{
		    if(p%2==1)
		        result *= n;	    
		    p >>=1;
		    n*=n;	    
		}
		return result;
	    }
	    public static void debug(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
	    void run() throws Exception {
			is = System.in;
			out = new PrintWriter(System.out);
			solve();
			out.flush();
		}
	   
	    public static void main(String[] args) throws Exception {
			new Thread(null, new Runnable() {
				public void run() {
					try {
						new code5().run();
					} catch (Exception e) {
						e.printStackTrace();
					}
				}
			}, "1", 1 << 26).start();
			
	    	//new code5().run();
		}
	    private byte[] inbuf = new byte[1024];
		public int lenbuf = 0, ptrbuf = 0;
	 
		private int readByte() {
			if (lenbuf == -1)
				throw new InputMismatchException();
			if (ptrbuf >= lenbuf) {
				ptrbuf = 0;
				try {
					lenbuf = is.read(inbuf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return -1;
			}
			return inbuf[ptrbuf++];
		}
	 
		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}
	 
		private int skip() {
			int b;
			while ((b = readByte()) != -1 && isSpaceChar(b));
			return b;
		}
	 
		private double nd() {
			return Double.parseDouble(ns());
		}
	 
		private char nc() {
			return (char) skip();
		}
	 
		private String ns() {
			int b = skip();
			StringBuilder sb = new StringBuilder();
			while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
	 
		private char[] ns(int n) {
			char[] buf = new char[n];
			int b = skip(), p = 0;
			while (p < n && !(isSpaceChar(b))) {
				buf[p++] = (char) b;
				b = readByte();
			}
			return n == p ? buf : Arrays.copyOf(buf, p);
		}
	 
		private char[][] nm(int n, int m) {
			char[][] map = new char[n][];
			for (int i = 0; i < n; i++)
				map[i] = ns(m);
			return map;
		}
	 
		private int[] na(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = ni();
			return a;
		}
		private long[] nl(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nl();
			return a;
		}
	 
		private int ni() {
			int num = 0, b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
	 
			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}
	 
		private long nl() {
			long num = 0;
			int b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
	 
			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}
	 
}