\(\large\textbf{Statement.}\)
求出最小的非负整数 \(m\)，使得：
\[\left|x-\sum_{i=0}^{m-1} x_{i \bmod n}\right|+\left|y-\sum_{i=0}^{m-1} y_{i \bmod n}\right|\le mk \]\(\large\textbf{Solution.}\)
考虑枚举 \(m \bmod n\)，然后求和就转化成了一段前缀和加上整个序列和的若干倍。
发现左边的式子是个下凸函数，而且是由三段线性函数组成的。只有在某对绝对值符号内的东西符号改变时斜率才会改变，可以求出改变时的横坐标，然后三段函数分别考虑。
对于一段函数，要求出线段上最靠左且在直线 \(y=nkx+ik\) 下方的点。
先判掉最左边的点满足条件和在不满足该情况下最右边的点不满足条件的情况，前者已经找到了最靠左的那个点，后者无解。
然后对于剩下的情况一定存在一个交点，求出交点的坐标然后就做完了。
时间复杂度 \(\mathcal O(n)\)。注意有多处要用到 __int128，另外如果直接调用 abs(__int128) 无法通过编译。
参考代码：
#include<bits/stdc++.h>
#define ll long long
#define mxn 100003
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
inline int read(){
int x=0;bool fl=0;char c=getchar();
while(!isdigit(c)){if(c=='-')fl=1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return fl?-x:x;
}
int t,n,k,x,y,a[mxn],b[mxn];
ll ans,ps,s1[mxn],s2[mxn];
inline __int128 abs(__int128 x){
return x<0?-x:x;
}
inline __int128 get(int i,ll j){
return abs(s1[i]+(__int128)s1[n]*j-x)+abs(s2[i]+(__int128)s2[n]*j-y);
}
void solve(int i,ll l,ll r){
if(l>r)return;
if(get(i,l)<=(i+(__int128)n*l)*k){
ans=min((__int128)ans,(__int128)l*n+i);
return;
}
if(get(i,r)>(i+(__int128)n*r)*k)return;
__int128 y1=get(i,l),y2=get(i,r),k1=(ll)n*k-(y2-y1)/(r-l);
ll ps=(get(i,l)-(i+(__int128)n*l)*k+k1-1)/k1+l;
ans=min((__int128)ans,(__int128)ps*n+i);
}
signed main(){
t=read();
while(t--){
n=read(),k=read(),x=read(),y=read();
rep(i,1,n){
a[i]=read(),b[i]=read();
s1[i]=s1[i-1]+a[i],s2[i]=s2[i-1]+b[i];
}
if(!x&&!y){
puts("0");
continue;
}
ans=5e18;
rep(i,0,n){
ll p1=max(s1[n]?(x-s1[i])/s1[n]:(ll)1e16,0ll),p2=max(s2[n]?(y-s2[i])/s2[n]:(ll)1e16,0ll);
if(p1>p2)swap(p1,p2);
solve(i,0,p1);
solve(i,p1+1,p2);
solve(i,p2+1,1e16);
}
if(ans==5e18)puts("-1");
else printf("%lld\n",ans);
}
return 0;
}