Problem: Vasya participates in a ski race along the X axis. The start is at point 0, and the finish is at L, that is, at a distance L meters from the start in the positive direction of the axis. Vasya has been training so hard that he can run one meter in exactly one second.

Besides, there are n take-off ramps on the track, each ramp is characterized by four numbers: 

  * xi represents the ramp's coordinate 
  * di represents from how many meters Vasya will land if he goes down this ramp 
  * ti represents the flight time in seconds 
  * pi is the number, indicating for how many meters Vasya should gather speed to get ready and fly off the ramp. As Vasya gathers speed, he should ski on the snow (that is, he should not be flying), but his speed still equals one meter per second. 



Vasya is allowed to move in any direction on the X axis, but he is prohibited to cross the start line, that is go to the negative semiaxis. Vasya himself chooses which take-off ramps he will use and in what order, that is, he is not obliged to take off from all the ramps he encounters. Specifically, Vasya can skip the ramp. It is guaranteed that xi + di ≤ L, that is, Vasya cannot cross the finish line in flight.

Vasya can jump from the ramp only in the positive direction of X axis. More formally, when using the i-th ramp, Vasya starts gathering speed at point xi - pi, jumps at point xi, and lands at point xi + di. He cannot use the ramp in opposite direction.

Your task is to find the minimum time that Vasya will spend to cover the distance.

Input

The first line contains two integers n and L (0 ≤ n ≤ 105, 1 ≤ L ≤ 109). Then n lines contain the descriptions of the ramps, each description is on a single line. Each description is a group of four non-negative integers xi, di, ti, pi (0 ≤ xi ≤ L, 1 ≤ di, ti, pi ≤ 109, xi + di ≤ L).

Output

Print in the first line the minimum time in seconds Vasya needs to complete the track. Print in the second line k — the number of take-off ramps that Vasya needs to use, and print on the third line of output k numbers the number the take-off ramps Vasya used in the order in which he used them. Print each number exactly once, separate the numbers with a space. The ramps are numbered starting from 1 in the order in which they are given in the input.

Examples

Input

2 20
5 10 5 5
4 16 1 7


Output

15
1
1 

Input

2 20
9 8 12 6
15 5 1 1


Output

16
1
2 

Note

In the first sample, Vasya cannot use ramp 2, because then he will need to gather speed starting from point -3, which is not permitted by the statement. The optimal option is using ramp 1, the resulting time is: moving to the point of gathering speed + gathering speed until reaching the takeoff ramp + flight time + moving to the finish line = 0 + 5 + 5 + 5 = 15.

In the second sample using ramp 1 is not optimal for Vasya as t1 > d1. The optimal option is using ramp 2, the resulting time is: moving to the point of gathering speed + gathering speed until reaching the takeoff ramp + flight time + moving to the finish line = 14 + 1 + 1 + 0 = 16.

Solution (in JAVA):

Solution:
import java.util.*;
import java.util.Collections.*;

public class D {

public static class Heap {
  int heap[][];
  int rev[];
  int size = 0;

  static int dummy[] = new int[]{-1,-1};

  public Heap(int n_items) {
    heap = new int[n_items][2];
    rev = new int[n_items];
    Arrays.fill(rev, -1);
  }

  int update(int priority, int item) {
    int idx = rev[item];
    if (idx == -1) { // add
      idx = size++;
      heap[idx][0] = priority;
      heap[idx][1] = item;
      rev[item] = idx;
      return heapify_up(idx);
    } else { // update
      int oldpriority = heap[idx][0];
      heap[idx][0] = priority;
      if (oldpriority > priority)
        return heapify_up(idx);
      else if (oldpriority < priority)
        return heapify_down(idx);
      return idx;
    }
  }

  int[] pop() {
    if (size == 0)
      return new int[]{-1,-1};
    remove_at(0);
    return heap[size];
  }

  int[] peek() {
    return size != 0 ? heap[0]: dummy;
  }

  int priority(int item) {
    int idx =  rev[item];
    return idx != -1 ? heap[rev[item]][0] : -1;
  }

  void remove_at(int idx) {
    swap(idx, --size);
    rev[heap[size][1]] = -1;
    heapify_down(idx);
  }

  int heapify_up(int idx) {
    while (idx != 0 && heap[(idx-1)/2][0] > heap[idx][0]) {
      swap(idx, (idx-1)/2);
      idx = (idx-1)/2;
    }
    return idx;
  }

  int heapify_down(int idx) {
    while (idx*2+1 < size) {
      int idx2 = idx*2+1;
      if (idx2+1 < size && heap[idx2][0] > heap[idx2+1][0])
        idx2+=1;
      if (heap[idx2][0] > heap[idx][0])
        break;
      swap(idx, idx2);
      idx = idx2;
    }
    return idx;
  }

  void swap(int idx1, int idx2) {
    if (idx1 == idx2) return;
    rev[heap[idx1][1]] = idx2;
    rev[heap[idx2][1]] = idx1;
    int temp[] = heap[idx1];
    heap[idx1] = heap[idx2];
    heap[idx2] = temp;
  }
}  


  static int N;
  static int L;

  static int NONE = 0;
  static int START = 1;
  static int END = 2;

  static int pos_of(long val) {
    if (val >= 0)
      return (int) (val / N);
    else
      return -pos_of(-val);
  }

  static int jump_id(long val) {
    if (val >= 0)
      return (int) (val % N);
    else
      return jump_id(-val);
  }

  static long pack(int pos, int jump_id) {
    if (pos >= 0)
      return (long)pos * N + jump_id;
    else
      return -pack(-pos, jump_id);
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    N = sc.nextInt();
    L = sc.nextInt();

    if (N == 0) {
      System.out.printf("%d\n0\n\n", L);
      return;
    }

    // indexed by node_id
    long jump_start[] = new long[N];
    // arbitrary index
    long jump_end[] = new long[N];
    
    // indexed by jump_id
    int jump_time[] = new int[N];
    // indexed by jump_id: points to node_id
    int next[] = new int[N];
    int next_weight[] = new int[N];
    // indexed by jump_id: points to node_id
    int prev[] = new int[N];
    int prev_weight[] = new int[N];
    // indexed by jump_id: points to node_id
    int jump_prev[] = new int[N];
    int jump_prev_weight[] = new int[N];
    // indexed by jump_id: points to node_id
    int jump_next[] = new int[N];
    int jump_next_weight[] = new int[N];

    for (int i = 0; i < N; ++i) {
      int x = sc.nextInt();
      int d = sc.nextInt();
      int t = sc.nextInt();
      int p = sc.nextInt();

      jump_start[i] = pack(x-p, i);
      jump_end[i] = pack(x+d, i);
      jump_time[i] = t+p;
    }

    Arrays.sort(jump_start);
    Arrays.sort(jump_end);
    
    int cur_end = N-1;
    int end_pos = pos_of(jump_end[cur_end]);
    int end_id = jump_id(jump_end[cur_end]);

    int start = N-1;
    for (int i = N - 1 ; i >= 0; start=i--) {
      int pos = pos_of(jump_start[i]);
      int jump = jump_id(jump_start[i]);
 
      int next_pos;

      if (i == N-1) {
        next_pos = L;
      } else {
        next_pos = pos_of(jump_start[i+1]);
      }

      next[jump] = i+1;
      next_weight[jump] = next_pos - pos;

      if (i != N-1) {
        int next_id = jump_id(jump_start[i+1]);
        if (pos >= 0) {
          prev[next_id] = i;
          prev_weight[next_id] = next_pos - pos;
        } else {
          prev[next_id] = -1;
        }
      }

      while (end_pos > pos && cur_end >=0) {
        jump_next[end_id] = i+1;
        jump_next_weight[end_id] = next_pos - end_pos + jump_time[end_id];

        if (pos >= 0) {
	  jump_prev[end_id] = i;
	  jump_prev_weight[end_id] = end_pos - pos + jump_time[end_id];
        } else {
          jump_prev[end_id] = -1;
        }

        cur_end -= 1;
        if (cur_end < 0) break;
        end_pos = pos_of(jump_end[cur_end]);
        end_id = jump_id(jump_end[cur_end]);
      }

      if ( pos < 0 ) break; // break after first negative pos
    }	
    prev[jump_id(jump_start[0])] = -1;

    int start_dist = pos_of(jump_start[start]);

    // indexed by node_id
    int min_dist[] = new int[N+1];
    // indexed by node_id: points to node_id
    int back_edge[] = new int[N+1];
    // indexed by node_id: points to jump_id
    int jump_from[] = new int[N+1];

    Arrays.fill(min_dist, -1);
    Arrays.fill(jump_from, -1);

    Heap h = new Heap(N+1);
    h.update(start_dist, start);

    while (h.size > 0) {
      int pair[] = h.pop();
      int dist = pair[0];
      int node = pair[1];

      min_dist[node] = dist;
      if (node == N) {
        break;
      }

      int pos = pos_of(jump_start[node]);
      int jump = jump_id(jump_start[node]);

      int neighbour;

      neighbour = next[jump];
      if (min_dist[neighbour] == -1) {
        int edge_weight = next_weight[jump];
        int cur_dist = h.priority(neighbour);
        if (cur_dist == -1 || cur_dist > dist+edge_weight) {
          h.update(dist+edge_weight, neighbour);
          back_edge[neighbour] = node;
          jump_from[neighbour] = -1;
        }
      }

      neighbour = prev[jump];
      if (neighbour != -1 && min_dist[neighbour] == -1) {
        int edge_weight = prev_weight[jump];
        int cur_dist = h.priority(neighbour);
        if (cur_dist == -1 || cur_dist > dist+edge_weight) {
          h.update(dist+edge_weight, neighbour);
          back_edge[neighbour] = node;
          jump_from[neighbour] = -1;
        }
      }

      neighbour = jump_next[jump];
      if (min_dist[neighbour] == -1) {
        int edge_weight = jump_next_weight[jump];
        int cur_dist = h.priority(neighbour);
        if (cur_dist == -1 || cur_dist > dist+edge_weight) {
          h.update(dist+edge_weight, neighbour);
          back_edge[neighbour] = node;
          jump_from[neighbour] = jump;
        }
      }

      neighbour = jump_prev[jump];
      if (neighbour != -1 && min_dist[neighbour] == -1) {
        int edge_weight = jump_prev_weight[jump];
        int cur_dist = h.priority(neighbour);
        if (cur_dist == -1 || cur_dist > dist+edge_weight) {
          h.update(dist+edge_weight, neighbour);
          back_edge[neighbour] = node;
          jump_from[neighbour] = jump;
        }
      } 
    }

    List<Integer> jumps = new ArrayList<Integer>();
    int cur = N;
    while (cur > start) {
      if (jump_from[cur] != -1) {
        jumps.add(jump_from[cur]);
      }
      cur = back_edge[cur];
    }

    System.out.printf("%d\n%d\n", min_dist[N], jumps.size());
    for (int i = jumps.size()-1; i >=0; --i) {
      System.out.printf("%d ", jumps.get(i)+1);
    }
    System.out.printf("\n");
  }
}