{"problem":{"name":"「REOI-1」调整圣剑","description":{"content":"具体而言，圣剑瑟尼欧里斯由 $n$ 个护符组成，每个护符有一个权值 $a_i$。威廉会进行 $k$ 次调整，每次调整一个护符，并获得与护符权值相等的疲惫值。 然而由于护符间的某种奇怪联系，威廉调整护符时有一些限制，这些限制形如 $(i,j,x,y)$，表示威廉必须在第 $i$ 次调整时调整前 $x$ 个护符中的一个 **或** 在第 $j$ 次调整时调整后 $y$ 个护符中的一个，否则圣剑就会崩","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8465"},"statements":[{"statement_type":"Markdown","content":"具体而言，圣剑瑟尼欧里斯由 $n$ 个护符组成，每个护符有一个权值 $a_i$。威廉会进行 $k$ 次调整，每次调整一个护符，并获得与护符权值相等的疲惫值。\n\n然而由于护符间的某种奇怪联系，威廉调整护符时有一些限制，这些限制形如 $(i,j,x,y)$，表示威廉必须在第 $i$ 次调整时调整前 $x$ 个护符中的一个 **或** 在第 $j$ 次调整时调整后 $y$ 个护符中的一个，否则圣剑就会崩溃。\n\n现在，珂朵莉想知道威廉在调整完所有护符后的最小疲惫值是多少。\n\n**注意每个护符可以调整不止一遍。**\n\n## Input\n\n第一行三个正整数 $n,k,q$。\n\n接下来一行 $n$ 个正整数 $a_1,a_2,a_3...a_n$。\n\n接下来 $q$ 行，每行 $4$ 个正整数 $i,j,x,y$。\n\n## Output\n\n一个数表示威廉疲惫值的最小值。\n\n[samples]\n\n## Background\n\n威廉从仓库搬出了瑟尼欧里斯。\n\n六十八号悬浮岛的边陲，稍稍隆起的小山丘上。\n\n风势平稳，空气澄净，星光柔和，各方面条件都合适的夜晚。\n\n他掀开盖着瑟尼欧里斯的布，让剑身透风。\n\n威廉注入些许魔力。太阳穴稍微会痛，不过这种程度还没什么大不了。\n\n瑟尼欧里斯顿时绽发柔和光芒。\n\n「——调整开始。」\n\n## Note\n\n样例解释：\n\n对于第一组样例，第一次选取 $a_2$ ，第二次选取 $a_2$ 。可以证明这是满足限制的最小值。\n\n对于第二组样例，第一次选择 $a_1$ ，第二次选择 $a_2$ 是为满足限制的最小值。\n\n对于 $24\\%$ 的数据：$1\\le n \\le 20,1\\le k,q \\le 14$ ；\n\n对于 $56\\%$ 的数据：$1\\le n \\le 100,1\\le k,q \\le 60$ ；\n\n对于 $80\\%$ 的数据：$1\\le n \\le 10^5, 1\\le k,q\\le 10^3$ ；\n\n对于 $100\\%$ 的数据：$1\\le n \\le 10^5,1\\le k,q\\le 10^4,1\\le a_i\\le 10^5$。\n\n对于每一次询问有 $1 \\le i,j \\le k$ , $1 \\le x,y \\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8465","tags":["洛谷原创","洛谷月赛"],"sample_group":[["3 2 1\n2 1 3\n1 2 2 2 \n","2"],["3 2 1\n2 1 3\n1 2 1 1 ","3"],["10 4 2\n5 2 1 3 3 1 4 5 5 3 \n4 3 1 7\n2 4 5 5","4"]],"created_at":"2026-03-03 11:09:25"}}