customerVip

Một nhà hàng bắt đầu mở cửa tại thời điểm 0 và đóng cửa tại thời điểm T=2x109.

Tại cửa ra vào nhà hàng có treo một bảng hiện thị số. Tại thời điểm 0, số trên bảng là 0 và cứ sau 1s số trên bảng giữ nguyên giá trị hoặc tăng 1 đơn vị hoặc giảm 1 đơn vị.
Lưu ý rằng bảng chỉ hiện thị được các số không âm.

Cho một ma trận customerList chứa thông tin về khách hàng, thông tin về mỗi khách hàng thứ i được biểu diễn thành một mảng gồm 3 số nguyên dương lần lượt là Ti, Si và Pi, trong đó:

• Ti là thời điểm mà vị khách vip thứ i sẽ đi qua nhà hàng.
• Số Pi là số yêu thích của người đó.
• Si là số tiền người đó sẽ vào và tiêu ở nhà hàng nếu như ở thời điểm người đó đi qua nhà hàng biển số trước cửa nhà hàng hiện đúng số người đó thích. Còn nếu không đúng số mà khách hàng thích thì họ sẽ không vào nhà hàng và không tiêu tiền.

Nhiệm vụ của bạn là hãy giúp nhà hàng tìm số tiền lớn nhất mà họ có thể thu được từ các khách hàng vip.

Ví dụ:

• Với customerList=[[2, 1, 3], [3, 2, 4], [1, 3, 10]], thì kết quả customerVip(customerList)=7.
  Giải thích:
  • Tại thời điểm T=0, bảng số hiện 0, thời điểm này chưa có khách hàng nào đi qua cửa hàng.
  • Tại thời điểm T=1, ta tăng biển thêm 1 đơn vị thành số 1, thời điểm này chưa có khách hàng nào đi qua cửa hàng.
  • Tại thời điểm T=2, thời điểm này có khách hàng thứ 0 đi qua cửa hàng, số yêu thích của người đó là S0 = 1, nên ta giữ nguyên biển ở số 1 để người đó vào và tiêu số tiền là P0 = 3.
  • Tại thời điểm T=3, thời điểm này có khách hàng thứ 1 đi qua cửa hàng, số yêu thích của người đó là S1 = 2, nên ta tăng biển thêm 1 đơn vị thành số 2 để người đó vào và tiêu số tiền là P1 = 4.
  • Vì sau 1s bảng chỉ giữ nguyên hoặc tăng, giảm 1 đơn vị nên từ thời điểm T=0 sang thời điểm T=1 bảng không thể hiển thị số 3 để đúng sở thích của khách hàng thứ 2 trong danh sách customerList.

        Tổng số tiền lớn nhất mà các vị khách vip trả cho nhà hàng sẽ là 7.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.1s (C++), 0.6s (Java và C#), 0.8s (Python, Go và Javascript).
• [Đầu vào] Matrix.interger customerList
  Danh sách khách hàng của nhà hàng. Mỗi phần tử trong danh sách là thông tin về một khách hàng
  0 <= customerList.length() <= 200
customerList[i].size() = 3
• [Đầu ra] Interger
  Tổng số tiền lớn nhất các vị khách vip có thể tiêu ở nhà hàng.