{"problem":{"name":"Intervals","description":{"content":"Consider a string of length $N$ consisting of `0` and `1`. The score for the string is calculated as follows: *   For each $i$ ($1 \\leq i \\leq M$), $a_i$ is added to the score if the string contains ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"dp_w"},"statements":[{"statement_type":"Markdown","content":"Consider a string of length $N$ consisting of `0` and `1`. The score for the string is calculated as follows:\n\n*   For each $i$ ($1 \\leq i \\leq M$), $a_i$ is added to the score if the string contains `1` at least once between the $l_i$\\-th and $r_i$\\-th characters (inclusive).\n\nFind the maximum possible score of a string.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 2 × 10^5$\n*   $1 \\leq M \\leq 2 × 10^5$\n*   $1 \\leq l_i \\leq r_i \\leq N$\n*   $|a_i| \\leq 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$l_1$ $r_1$ $a_1$\n$l_2$ $r_2$ $a_2$\n$:$\n$l_M$ $r_M$ $a_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dp_w","tags":[],"sample_group":[["5 3\n1 3 10\n2 4 -10\n3 5 10","20\n\nThe score for `10001` is $a_1 + a_3 = 10 + 10 = 20$."],["3 4\n1 3 100\n1 1 -10\n2 2 -20\n3 3 -30","90\n\nThe score for `100` is $a_1 + a_2 = 100 + (-10) = 90$."],["1 1\n1 1 -10","0\n\nThe score for `0` is $0$."],["1 5\n1 1 1000000000\n1 1 1000000000\n1 1 1000000000\n1 1 1000000000\n1 1 1000000000","5000000000\n\nThe answer may not fit into a 32-bit integer type."],["6 8\n5 5 3\n1 1 10\n1 6 -8\n3 6 5\n3 4 9\n5 5 -2\n1 3 -6\n4 6 -7","10\n\nFor example, the score for `101000` is $a_2 + a_3 + a_4 + a_5 + a_7 = 10 + (-8) + 5 + 9 + (-6) = 10$."]],"created_at":"2026-03-03 11:01:14"}}