游戏有n个小朋友参加大家围坐着一个有m个座位的巨大圆桌进行游戏，座位从1到m顺时针编号。第i个小朋友在第s个座位就座。

老师在游戏前对游戏进行了p个预测。每一个预测的形式是(a_i,b_i)，表示第a_i个小朋友在第b_i秒内取得了一次胜利。

已知当一个小朋友取得一次胜利时，就有一个糖果会被发给这个小朋友。如果糖果迟迟未到，小朋友就会失望。如果一个小朋友在第ta秒内解出了一题，在第tb秒内糖果送到他们的座位上，那么这个小朋友的失望值就加tb-ta。为了及时发放糖果，老师安排了一名糖果发放者。

在游戏开始时，也就是在第一秒开始的时候，糖果发放者将站在第k个座位旁，并开始围绕着桌子移动。如果糖果发放者经过一个小朋友而这个小朋友在糖果发放者上次经过之后获得了几次胜利，那么糖果发放者就将把这个小朋友应得的糖果给这个小朋友。在每一秒中，下列事件将按顺序发生：
(1)糖果发放者移动到下一个座位旁。也就是说，如果糖果发放者当前在第i(1≤i<m)个座位旁，他将移动到第i+1个座位旁；如果糖果发放者当前在第m个座位旁，他就移动到第1个座位旁。
(2)根据老师的预测，小朋友们获得了一些胜利。
(3)如果糖果发放者所在的座位的小朋友获得了胜利，糖果发放者就将糖果放在当前的座位上。

老师希望所有小朋友的总的失望值最小。请选择糖果发放者的起始位置k，并根据老师的预测，计算所有小朋友的总的失望值的最小值。

输入有多个测试用例。输入的第一行是一个整数T,表示测试用例的个数。

对于每个测试用例：

第一行给出三个整数n、m和p(1≤n≤10⁵,n≤m≤10⁹,1≤p≤10⁵)，分别指出小朋友的数目、座位的数目和预测的数目。

第二行给出n个整数s₁,s₂,…,s_n(1≤s_i≤m并且对于所有的i≠j,s_i≠s_j)，表示每个小朋友的座位号。

接下来的p行，每行给出两个整数a_i和b_i(1≤a_i≤n,1≤b_i≤10⁹)，表示按老师的预测，第a_i个小朋友在时间b_i秒获得一次胜利。

本题设定，所有的测试用例的n的和与p的和都不会超过5×10⁵。