题目链接：http://hihocoder.com/problemset/problem/1831

时间限制:1000ms

单点时限:1000ms

内存限制:256MB

描述

80 Days is an interesting game based on Jules Verne's science fiction "Around the World in Eighty Days". In this game, you have to manage the limited money and time.

Now we simplified the game as below:

There are n cities on a circle around the world which are numbered from 1 to n by their order on the circle. When you reach the city i at the first time, you will get ai dollars (ai can even be negative), and if you want to go to the next city on the circle, you should pay bi dollars. At the beginning you have c dollars.

The goal of this game is to choose a city as start point, then go along the circle and visit all the city once, and finally return to the start point. During the trip, the money you have must be no less than zero.

Here comes a question: to complete the trip, which city will you choose to be the start city?

If there are multiple answers, please output the one with the smallest number.

输入

The first line of the input is an integer T (T ≤ 100), the number of test cases.

For each test case, the first line contains two integers n and c (1 ≤ n ≤ 106, 0 ≤ c ≤ 109).  The second line contains n integers a1, …, an  (-109 ≤ ai ≤ 109), and the third line contains n integers b1, …, bn (0 ≤ bi ≤ 109).

It's guaranteed that the sum of n of all test cases is less than 106

输出

For each test case, output the start city you should choose.

提示

For test case 1, both city 2 and 3 could be chosen as start point, 2 has smaller number. But if you start at city 1, you can't go anywhere.

For test case 2, start from which city seems doesn't matter, you just don't have enough money to complete a trip.

样例输入

2
3 0
3 4 5
5 4 3
3 100
-3 -4 -5
30 40 50

样例输出

2
-1

EmacsNormalVim

题目大意：T组数据，每组数据n，c（初始金币数量），n个城市（编号1-n）按输入顺序围成一个环，每个城市进入获得ai金币，出城市失去bi金币（都可能是负数）问从哪个城市开始走，能保证走完这个环时不出现负的金币持有量，多个答案取最小的那个编号（如果没有符合要求的，输出-1）：

很容易就想到把一个环展开，1-n-2*n，取其中的n连续的n个数就是一个环；

然后对于每个点，如果符合要求，则添加进队列，如果不符合要求，则取出队首元素，再次查看；

代码比较简单：

//#pragma comment(linker, "/STACK:1024000000,1024000000") 
 
#include<stdio.h>
#include<string.h>  
#include<math.h>  
#include<stdlib.h>

//#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<fstream>
#include<iostream>  
#include<algorithm>  
using namespace std;  
 
#define ll long long  
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b) 
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//std::ios::sync_with_stdio(false);
const int MAXN=1e6+10;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;

ll arr1[MAXN<<1],arr2[MAXN<<1];
deque<int> que;
//void intt()
//{
//	clean(arr1,0);
//	clean(arr2,0);
//}
int main()
{
	std::ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
    	//intt();
    	int n;
    	ll sum;
    	cin>>n>>sum;
    	for(int i=1;i<=n;++i)//输入in 
    		cin>>arr1[i];
    	for(int i=n+1;i<=n+n;++i)//扩展in 
    		arr1[i]=arr1[i-n];
    	for(int i=1;i<=n;++i)//输入out 
    		cin>>arr2[i];
    	for(int i=n+1;i<=n+n;++i)//扩展out 
    		arr2[i]=arr2[i-n];
    	
    	while(que.size())
    		que.pop_back();
    	bool flag=0;
    	for(int i=1;i<=n+n;++i)
    	{
    		if(sum+arr1[i]-arr2[i]>=0)//符合要求 
    		{
    			que.push_back(i);
    			sum=sum+arr1[i]-arr2[i];
    			if(que.size()>=n)
    			{
    				flag=1;
    				cout<<que.front()<<endl;
    				break;
				}
			}
			else//不符合要求 
			{
				while(sum+arr1[i]-arr2[i]<0&&que.size()>0)
				{
					sum=sum-arr1[que.front()]+arr2[que.front()];
					que.pop_front();
				}
				//直到符合要求||从新开始 
				if(sum+arr1[i]-arr2[i]>=0)
				{
					que.push_back(i);
					sum=sum+arr1[i]-arr2[i];
				}
				if(que.size()>=n)
				{
					flag=1;
					cout<<que.front()<<endl;
					break;
				}
			}
		}
		if(!flag)
			cout<<-1<<endl;
	}
	return 0;
}