Hành trình qua các trạm xăng

General
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Có $N$ trạm xăng nằm trên một vòng tròn, đánh số từ $0$ đến $N - 1$. Tại trạm $i$ bạn được đổ $G_i$ lít xăng, và để đi từ trạm $i$ tới trạm $(i + 1) \bmod N$ cần tốn $C_i$ lít xăng. Ban đầu bình xăng rỗng (dung tích bình vô hạn). Hãy tìm chỉ số trạm xuất phát nhỏ nhất sao cho bạn có thể đi hết một vòng tròn. Nếu không thể, in ra -1.

Dữ liệu vào

Dòng đầu chứa số nguyên $N$. Dòng thứ hai chứa $N$ số nguyên $G_0, G_1, \dots, G_{N-1}$. Dòng thứ ba chứa $N$ số nguyên $C_0, C_1, \dots, C_{N-1}$.

Dữ liệu ra

In ra chỉ số trạm xuất phát nhỏ nhất (từ $0$ đến $N-1$), hoặc -1 nếu không có.

Ví dụ
Input Output
5
1 2 3 4 5
3 4 5 1 2
3
3
2 3 4
3 4 3
-1
Giới hạn
  • $1 \le N \le 10^5$.
  • $0 \le G_i, C_i \le 10^9$.
Draft saved