{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eC-bacteria takes charge of two kinds of videos: ’The Collection of Silly Games’ and ’The Collection of Horrible Games’.\u003cbr\u003eFor simplicity’s sake, they will be called as videoA and videoB.\u003cbr\u003eThere are some people who want to watch videos during today, and they will be happy after watching videos of C-bacteria.\u003cbr\u003eThere are n hours a day, m videos are going to be show, and the number of people is K.\u003cbr\u003eEvery video has a type(videoA or videoB), a running time, and the degree of happi- ness after someone watching whole of it.\u003cbr\u003ePeople can watch videos continuous(If one video is running on 2pm to 3pm and another is 3pm to 5pm, people can watch both of them).\u003cbr\u003eBut each video only allows one person for watching.\u003cbr\u003eFor a single person, it’s better to watch two kinds to videos alternately, or he will lose W happiness.\u003cbr\u003eFor example, if the order of video is ’videoA, videoB, videoA, videoB, …’ or ’B, A, B, A, B, …’, he won’t lose happiness; But if the order of video is ’A, B, B, B, A, B, A, A’, he will lose 3W happiness.\u003cbr\u003eNow you have to help people to maximization the sum of the degree of happiness.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Multiple query.\u003cbr\u003eOn the first line, there is a positive integer T, which describe the number of data. Next there are T groups of data.\u003cbr\u003efor each group, the first line have four positive integers n, m, K, W : n hours a day, m videos, K people, lose W happiness when watching same videos).\u003cbr\u003eand then, the next m line will describe m videos, four positive integers each line S, T, w, op : video is the begin at S and end at T, the happiness that people can get is w, and op describe it’s tpye(op\u003d0 for videoA and op\u003d1 for videoB).\u003cbr\u003eThere is a blank line before each groups of data.\u003cbr\u003eT\u0026lt;\u003d20, n\u0026lt;\u003d200, m\u0026lt;\u003d200, K\u0026lt;\u003d200, W\u0026lt;\u003d20, 1\u0026lt;\u003dS\u0026lt;T\u0026lt;\u003dn, W\u0026lt;\u003dw\u0026lt;\u003d1000,\u003cbr\u003eop\u003d0 or op\u003d1\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"Your output should include T lines, for each line, output the maximum happiness for the corresponding datum."}},{"title":"Sample","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\u003e2\r\n10 3 1 10\r\n1 5 1000 0\r\n5 10 1000 1\r\n3 9 10 0\r\n10 3 1 10\r\n1 5 1000 0\r\n5 10 1000 0\r\n3 9 10 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2000\r\n1990\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}