Người thắng cuộc theo diễn biến điểm

Bối cảnh và bài toán

Một trò chơi trực tuyến ghi lại n sự kiện thay đổi điểm theo thời gian. Mỗi sự kiện name delta cộng delta vào điểm của người chơi name; delta có thể âm vì người chơi có thể bị trừ điểm. Ban đầu mọi người có 0 điểm.

Sau khi tất cả sự kiện kết thúc, gọi M là điểm cuối lớn nhất. Nếu chỉ có một người đạt M, người đó thắng. Nếu nhiều người cùng kết thúc với M, hệ thống dùng lịch sử diễn biến để phá hòa: người thắng là người đầu tiên trong dòng thời gian đạt điểm tạm thời >= M, với điều kiện người đó cuối cùng cũng có điểm M.

Đảm bảo M > 0.

Yêu cầu

Xác định tên người thắng theo đúng quy tắc trên.

Input

• Dòng 1: n.
• n dòng tiếp theo: name delta theo thứ tự thời gian.

Output

Tên người thắng.

Ràng buộc

• 1 <= n <= 2 * 10^5
• 1 <= |name| <= 32, chỉ gồm chữ thường a..z
• -10^9 <= delta <= 10^9

Chấm điểm

Ví dụ 1

Input

3
mike 3
andrew 5
mike 2

Output

andrew

Giải thích. Mike và Andrew đều kết thúc với 5 điểm. Andrew đạt ngưỡng 5 ở lượt 2, còn Mike tới lượt 3 mới đạt 5, nên Andrew thắng.

Ví dụ 2

Input

5
a 10
b 7
a -5
b -2
c 1

Output

a

Giải thích. a và b đều kết thúc với 5 điểm, nên M=5. Người chơi a đã đạt ít nhất 5 điểm ngay ở lượt đầu và cuối cùng vẫn thuộc nhóm có điểm M, vì vậy a thắng.

Thông tin bài tập

• Yêu cầu: Decision Note đầy đủ.

Nguồn: Phỏng theo Codeforces — 2A Winner.
Tham khảo: https://codeforces.com/problemset/problem/2/A
Ghi chú biên tập: Biên tập lại ngữ cảnh/constraints và chuẩn hóa theo lộ trình FULLHOUSE DEV; giữ bản chất yêu cầu của bài nguồn.