{"trustable":true,"sections":[{"title":"Background","value":{"format":"MD","content":"The Chinese exam is over, and the grades are still problematic as always."}},{"title":"Description","value":{"format":"MD","content":"The Chinese teacher always makes mistakes in grading, so when she corrects the grades, she always gets exhausted. She always has to repeatedly increase the scores for certain students and pay attention to the minimum score. Can you help her?"}},{"title":"Input","value":{"format":"MD","content":"The first line contains two integers $n$, $p$, representing the number of students and the number of times the score is increased.\n\nThe second line contains $n$ numbers, $a_1 \\sim a_n$, representing the initial scores of each student.\n\nThe next $p$ lines each contain three numbers, $x$, $y$, $z$, representing adding $z$ points to each student from the $x$th to the $y$th student."}},{"title":"Output","value":{"format":"MD","content":"Output a single line representing the minimum score of the whole class after the score changes."}},{"title":"Sample 1","value":{"format":"MD","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\u003e3 2\n1 1 1\n1 2 1\n2 3 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Hint","value":{"format":"MD","content":"For data $40\\%$, there are $n \\le 10^3$.\n\nFor data $60\\%$, there are $n \\le 10^4$.\n\nFor data $80\\%$, there are $n \\le 10^5$.\n\nFor data $100\\%$, there are $n \\le 5\\times 10^6$, $p \\le n$, with student initial scores $ \\le 100$, $z \\le 100$."}}]}