You are a paparazzi working in Manhattan.

Manhattan has r south-to-north streets, denoted by numbers 1, 2,…, r in order from west to east, and r west-to-east streets, denoted by numbers 1,2,…,r in order from south to north. Each of the r south-to-north streets intersects each of the r west-to-east streets; the intersection between the x-th south-to-north street and the y-th west-to-east street is denoted by (x, y). In order to move from the intersection (x,y) to the intersection (x', y') you need |x-x'|+|y-y'| minutes.

You know about the presence of n celebrities in the city and you want to take photos of as many of them as possible. More precisely, for each i=1,..., n, you know that the i-th celebrity will be at the intersection (x_i, y_i) in exactly t_i minutes from now (and he will stay there for a very short time, so you may take a photo of him only if at the t_i-th minute from now you are at the intersection (x_i, y_i)). You are very good at your job, so you are able to take photos instantaneously. You know that t_i < t_{i+1} for any i=1,2,…, n-1.

Currently you are at your office, which is located at the intersection (1, 1). If you plan your working day optimally, what is the maximum number of celebrities you can take a photo of?

Input

The first line of the input contains two positive integers r, n (1≤ r≤ 500, 1≤ n≤ 100,000) – the number of south-to-north/west-to-east streets and the number of celebrities.

Then n lines follow, each describing the appearance of a celebrity. The i-th of these lines contains 3 positive integers t_i, x_i, y_i (1≤ t_i≤ 1,000,000, 1≤ x_i, y_i≤ r) — denoting that the i-th celebrity will appear at the intersection (x_i, y_i) in t_i minutes from now.

It is guaranteed that t_i<t_{i+1} for any i=1,2,…, n-1.

Output

Print a single integer, the maximum number of celebrities you can take a photo of.

Examples

Input


10 1
11 6 8


Output


0


Input


6 9
1 2 6
7 5 1
8 5 5
10 3 1
12 4 4
13 6 2
17 6 6
20 1 4
21 5 4


Output


4


Input


10 4
1 2 1
5 10 9
13 8 8
15 9 9


Output


1


Input


500 10
69 477 122
73 186 235
341 101 145
372 77 497
390 117 440
494 471 37
522 300 498
682 149 379
821 486 359
855 157 386


Output


3

Note

Explanation of the first testcase: There is only one celebrity in the city, and he will be at intersection (6,8) exactly 11 minutes after the beginning of the working day. Since you are initially at (1,1) and you need |1-6|+|1-8|=5+7=12 minutes to reach (6,8) you cannot take a photo of the celebrity. Thus you cannot get any photo and the answer is 0.

Explanation of the second testcase: One way to take 4 photos (which is the maximum possible) is to take photos of celebrities with indexes 3, 5, 7, 9 (see the image for a visualization of the strategy): 

  * To move from the office at (1,1) to the intersection (5,5) you need |1-5|+|1-5|=4+4=8 minutes, so you arrive at minute 8 and you are just in time to take a photo of celebrity 3. 
  * Then, just after you have taken a photo of celebrity 3, you move toward the intersection (4,4). You need |5-4|+|5-4|=1+1=2 minutes to go there, so you arrive at minute 8+2=10 and you wait until minute 12, when celebrity 5 appears. 
  * Then, just after you have taken a photo of celebrity 5, you go to the intersection (6,6). You need |4-6|+|4-6|=2+2=4 minutes to go there, so you arrive at minute 12+4=16 and you wait until minute 17, when celebrity 7 appears. 
  * Then, just after you have taken a photo of celebrity 7, you go to the intersection (5,4). You need |6-5|+|6-4|=1+2=3 minutes to go there, so you arrive at minute 17+3=20 and you wait until minute 21 to take a photo of celebrity 9. 

<image>

Explanation of the third testcase: The only way to take 1 photo (which is the maximum possible) is to take a photo of the celebrity with index 1 (since |2-1|+|1-1|=1, you can be at intersection (2,1) after exactly one minute, hence you are just in time to take a photo of celebrity 1).

Explanation of the fourth testcase: One way to take 3 photos (which is the maximum possible) is to take photos of celebrities with indexes 3, 8, 10: 

  * To move from the office at (1,1) to the intersection (101,145) you need |1-101|+|1-145|=100+144=244 minutes, so you can manage to be there when the celebrity 3 appears (at minute 341). 
  * Then, just after you have taken a photo of celebrity 3, you move toward the intersection (149,379). You need |101-149|+|145-379|=282 minutes to go there, so you arrive at minute 341+282=623 and you wait until minute 682, when celebrity 8 appears. 
  * Then, just after you have taken a photo of celebrity 8, you go to the intersection (157,386). You need |149-157|+|379-386|=8+7=15 minutes to go there, so you arrive at minute 682+15=697 and you wait until minute 855 to take a photo of celebrity 10. 
import java.io.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class cf1427c {

    public static void main(String[] args) throws IOException {
        int r = rni(), n = ni(), t[] = new int[n + 1], x[] = new int[n + 1], y[] = new int[n + 1], dp[] = new int[n + 1], min = 0;
        x[0] = y[0] = 1;
        for (int i = 1; i <= n; ++i) {
            t[i] = rni();
            x[i] = ni();
            y[i] = ni();
            dp[i] = -n;
            for (int j = max(0, i - r - r); j < i; ++j) {
                if (t[i] - t[j] >= abs(x[i] - x[j]) + abs(y[i] - y[j])) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            if (i - r - r >= 0) {
                min = max(min, dp[i - r - r]);
                dp[i] = max(dp[i], min + 1);
            }
        }
        // prln(dp);
        prln(maxof(dp));
        close();
    }

    static BufferedReader __in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter __out = new PrintWriter(new OutputStreamWriter(System.out));
    static StringTokenizer input;
    static Random __rand = new Random();

    // references
    // IBIG = 1e9 + 7
    // IMAX ~= 2e9
    // LMAX ~= 9e18

    // constants
    static final int IBIG = 1000000007;
    static final int IMAX = 2147483647;
    static final int IMIN = -2147483648;
    static final long LMAX = 9223372036854775807L;
    static final long LMIN = -9223372036854775808L;
    // math util
    static int minof(int a, int b, int c) {return min(a, min(b, c));}
    static int minof(int... x) {if (x.length == 1) return x[0]; if (x.length == 2) return min(x[0], x[1]); if (x.length == 3) return min(x[0], min(x[1], x[2])); int min = x[0]; for (int i = 1; i < x.length; ++i) if (x[i] < min) min = x[i]; return min;}
    static long minof(long a, long b, long c) {return min(a, min(b, c));}
    static long minof(long... x) {if (x.length == 1) return x[0]; if (x.length == 2) return min(x[0], x[1]); if (x.length == 3) return min(x[0], min(x[1], x[2])); long min = x[0]; for (int i = 1; i < x.length; ++i) if (x[i] < min) min = x[i]; return min;}
    static int maxof(int a, int b, int c) {return max(a, max(b, c));}
    static int maxof(int... x) {if (x.length == 1) return x[0]; if (x.length == 2) return max(x[0], x[1]); if (x.length == 3) return max(x[0], max(x[1], x[2])); int max = x[0]; for (int i = 1; i < x.length; ++i) if (x[i] > max) max = x[i]; return max;}
    static long maxof(long a, long b, long c) {return max(a, max(b, c));}
    static long maxof(long... x) {if (x.length == 1) return x[0]; if (x.length == 2) return max(x[0], x[1]); if (x.length == 3) return max(x[0], max(x[1], x[2])); long max = x[0]; for (int i = 1; i < x.length; ++i) if (x[i] > max) max = x[i]; return max;}
    static int powi(int a, int b) {if (a == 0) return 0; int ans = 1; while (b > 0) {if ((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
    static long powl(long a, int b) {if (a == 0) return 0; long ans = 1; while (b > 0) {if ((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
    static int fli(double d) {return (int) d;}
    static int cei(double d) {return (int) ceil(d);}
    static long fll(double d) {return (long) d;}
    static long cel(double d) {return (long) ceil(d);}
    static int gcf(int a, int b) {return b == 0 ? a : gcf(b, a % b);}
    static long gcf(long a, long b) {return b == 0 ? a : gcf(b, a % b);}
    static int lcm(int a, int b) {return a * b / gcf(a, b);}
    static long lcm(long a, long b) {return a * b / gcf(a, b);}
    static int randInt(int min, int max) {return __rand.nextInt(max - min + 1) + min;}
    static long mix(long x) {x += 0x9e3779b97f4a7c15L; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9L; x = (x ^ (x >> 27)) * 0x94d049bb133111ebL; return x ^ (x >> 31);}
    // array util
    static void reverse(int[] a) {for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {int swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(long[] a) {for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {long swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(double[] a) {for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {double swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(char[] a) {for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {char swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void shuffle(int[] a) {int n = a.length - 1; for (int i = 0; i < n; ++i) {int ind = randInt(i, n); int swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(long[] a) {int n = a.length - 1; for (int i = 0; i < n; ++i) {int ind = randInt(i, n); long swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(double[] a) {int n = a.length - 1; for (int i = 0; i < n; ++i) {int ind = randInt(i, n); double swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void rsort(int[] a) {shuffle(a); sort(a);}
    static void rsort(long[] a) {shuffle(a); sort(a);}
    static void rsort(double[] a) {shuffle(a); sort(a);}
    static int[] copy(int[] a) {int[] ans = new int[a.length]; for (int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
    static long[] copy(long[] a) {long[] ans = new long[a.length]; for (int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
    static double[] copy(double[] a) {double[] ans = new double[a.length]; for (int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
    static char[] copy(char[] a) {char[] ans = new char[a.length]; for (int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
    // input
    static void r() throws IOException {input = new StringTokenizer(rline());}
    static int ri() throws IOException {return Integer.parseInt(rline());}
    static long rl() throws IOException {return Long.parseLong(rline());}
    static double rd() throws IOException {return Double.parseDouble(rline());}
    static int[] ria(int n) throws IOException {int[] a = new int[n]; r(); for (int i = 0; i < n; ++i) a[i] = ni(); return a;}
    static int[] riam1(int n) throws IOException {int[] a = new int[n]; r(); for (int i = 0; i < n; ++i) a[i] = ni() - 1; return a;}
    static long[] rla(int n) throws IOException {long[] a = new long[n]; r(); for (int i = 0; i < n; ++i) a[i] = nl(); return a;}
    static double[] rda(int n) throws IOException {double[] a = new double[n]; r(); for (int i = 0; i < n; ++i) a[i] = nd(); return a;}
    static char[] rcha() throws IOException {return rline().toCharArray();}
    static String rline() throws IOException {return __in.readLine();}
    static String n() {return input.nextToken();}
    static int rni() throws IOException {r(); return ni();}
    static int ni() {return Integer.parseInt(n());}
    static long rnl() throws IOException {r(); return nl();}
    static long nl() {return Long.parseLong(n());}
    static double rnd() throws IOException {r(); return nd();}
    static double nd() {return Double.parseDouble(n());}
    // output
    static void pr(int i) {__out.print(i);}
    static void prln(int i) {__out.println(i);}
    static void pr(long l) {__out.print(l);}
    static void prln(long l) {__out.println(l);}
    static void pr(double d) {__out.print(d);}
    static void prln(double d) {__out.println(d);}
    static void pr(char c) {__out.print(c);}
    static void prln(char c) {__out.println(c);}
    static void pr(char[] s) {__out.print(new String(s));}
    static void prln(char[] s) {__out.println(new String(s));}
    static void pr(String s) {__out.print(s);}
    static void prln(String s) {__out.println(s);}
    static void pr(Object o) {__out.print(o);}
    static void prln(Object o) {__out.println(o);}
    static void prln() {__out.println();}
    static void pryes() {prln("yes");}
    static void pry() {prln("Yes");}
    static void prY() {prln("YES");}
    static void prno() {prln("no");}
    static void prn() {prln("No");}
    static void prN() {prln("NO");}
    static boolean pryesno(boolean b) {prln(b ? "yes" : "no"); return b;};
    static boolean pryn(boolean b) {prln(b ? "Yes" : "No"); return b;}
    static boolean prYN(boolean b) {prln(b ? "YES" : "NO"); return b;}
    static void prln(int... a) {for (int i = 0, len = a.length - 1; i < len; pr(a[i]), pr(' '), ++i); if (a.length > 0) prln(a[a.length - 1]); else prln();}
    static void prln(long... a) {for (int i = 0, len = a.length - 1; i < len; pr(a[i]), pr(' '), ++i); if (a.length > 0) prln(a[a.length - 1]); else prln();}
    static void prln(double... a) {for (int i = 0, len = a.length - 1; i < len; pr(a[i]), pr(' '), ++i); if (a.length > 0) prln(a[a.length - 1]); else prln();}
    static <T> void prln(Collection<T> c) {int n = c.size() - 1; Iterator<T> iter = c.iterator(); for (int i = 0; i < n; pr(iter.next()), pr(' '), ++i); if (n >= 0) prln(iter.next()); else prln();}
    static void h() {prln("hlfd"); flush();}
    static void flush() {__out.flush();}
    static void close() {__out.close();}
}