{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAn automobile factory has a car production line. Now the market is oversupply and the production line is often shut down. To make full use of resources, the manager divides the entire production line into $N$ parts $(1...N)$. Some continuous parts can produce sub-products. And each of sub-products has their own value. The manager will use spare time to produce sub-products to make money. Because of the limited spare time, each part of the production line could only work at most $K$ times. And Because of the limited materials, each of the sub-products could be produced only once. The manager wants to know the maximum value could he make by produce sub-products.\u003c/p\u003e\u003ch3\u003eInput\u003c/h3\u003e\u003cp\u003eThe first line of input is $T$, the number of test case.\u003c/p\u003e\u003cp\u003eThe first line of each test case contains three integers, $N, K$ and $M$. ($M$ is the number of different sub-product).\u003c/p\u003e\u003cp\u003eThe next $M$ lines each contain three integers $A_i, B_i, W_i$ describing a sub-product. The sub-product has value $W_i$. Only $A_i$ to $B_i$ parts work simultaneously will the sub-product be produced (include $A_i$ to $B_i$).\u003c/p\u003e\u003cp\u003e$1 \\le T \\le 100$\u003c/p\u003e\u003cp\u003e$1 \\le K \\le M \\le 200$\u003c/p\u003e\u003cp\u003e$1 \\le N \\le 10^5$\u003c/p\u003e\u003cp\u003e$1 \\le A_i \\le B_i \\le N$\u003c/p\u003e\u003cp\u003e$1 \\le W_i \\le 10^5$\u003c/p\u003e\u003ch3\u003eOutput\u003c/h3\u003e\u003cp\u003eFor each test case output the maximum value in a separate line.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n10 1 3\n1 2 2\n2 3 4\n3 4 8\n10 1 3\n1 3 2\n2 3 4\n3 4 8\n100000 1 3\n1 100000 100000\n1 2 3\n100 200 300\n100000 2 3\n1 100000 100000\n1 150 301\n100 200 300\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\n8\n100000\n100301\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}