{"raw_statement":[{"iden":"background","content":"威廉从仓库搬出了瑟尼欧里斯。\n\n六十八号悬浮岛的边陲，稍稍隆起的小山丘上。\n\n风势平稳，空气澄净，星光柔和，各方面条件都合适的夜晚。\n\n他掀开盖着瑟尼欧里斯的布，让剑身透风。\n\n威廉注入些许魔力。太阳穴稍微会痛，不过这种程度还没什么大不了。\n\n瑟尼欧里斯顿时绽发柔和光芒。\n\n「——调整开始。」\n"},{"iden":"statement","content":"具体而言，圣剑瑟尼欧里斯由 $n$ 个护符组成，每个护符有一个权值 $a_i$。威廉会进行 $k$ 次调整，每次调整一个护符，并获得与护符权值相等的疲惫值。\n\n然而由于护符间的某种奇怪联系，威廉调整护符时有一些限制，这些限制形如 $(i,j,x,y)$，表示威廉必须在第 $i$ 次调整时调整前 $x$ 个护符中的一个 **或** 在第 $j$ 次调整时调整后 $y$ 个护符中的一个，否则圣剑就会崩溃。\n\n现在，珂朵莉想知道威廉在调整完所有护符后的最小疲惫值是多少。\n\n**注意每个护符可以调整不止一遍。**"},{"iden":"input","content":"第一行三个正整数 $n,k,q$。\n\n接下来一行 $n$ 个正整数 $a_1,a_2,a_3...a_n$。\n\n接下来 $q$ 行，每行 $4$ 个正整数 $i,j,x,y$。"},{"iden":"output","content":"一个数表示威廉疲惫值的最小值。"},{"iden":"note","content":"样例解释：\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$。"}],"translated_statement":null,"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"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}