{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"## Mô tả Đề bài\nBạn cần xử lý thông tin thuê phòng trong $n$ ngày của khách sạn, trong đó ngày thứ $i$ khách sạn có $r_i$ phòng trống để cho thuê. Có tổng cộng $m$ người gọi điện đặt phòng, yêu cầu của mỗi người được mô tả bằng ba số nguyên dương $d_j,s_j,t_j$, lần lượt biểu thị người này cần thuê phòng từ ngày thứ $s_j$ đến ngày thứ $t_j$ (bao gồm cả ngày thứ $s_j$ và $t_j$), mỗi ngày cần thuê tất cả là $d_j$ phòng.\n\nNguyên tắc thuê phòng là người nào gọi đến trước được phục vụ trước, nghĩa là chúng ta cần cho thuê theo thứ tự các đơn đặt hàng. Nếu không thể đáp ứng được yêu cầu của người nào đó thì việc cho thuê phòng phải dừng lại. Nghĩa là với người thuê thứ $j$, từ ngày thứ $s_j$ đến ngày thứ $t_j$ có ít nhất một ngày mà không có đủ $d_j$ phòng cho thuê thì phải thông báo cho khách này.\n\nHãy lập trình tính xem liệu có khách hàng nào mà ta không thể đáp ứng yêu cầu hay không.\n\n## Dữ liệu\n- Dòng đầu tiên chứa hai số nguyên dương $n,m$, biểu thị số ngày và số lượng khách thuê phòng.\n- Dòng thứ hai chứa $n$ số nguyên dương, trong đó số thứ $i$ là $r_i$, biểu thị số lượng phòng trống có thể cho thuê được trong ngày thứ $i$.\n- Tiếp theo là $m$ dòng, mỗi dòng chứa ba số nguyên dương $d_j,s_j,t_j$, biểu thị số lượng phòng cần thuê, ngày bắt đầu và kết thúc thuê. Mỗi dòng gồm hai số liền kề được phân cách bởi một khoảng trắng. Số ngày và đơn hàng đều được đánh số bắt đầu từ $1$.\n\n## Kết quả\n- Nếu có thể thoả mãn yêu cầu của tất cả các khách hàng, thì chỉ in ra một dòng, chứa một số nguyên $0$. Ngược lại, in ra trên hai dòng, dòng đầu tiên chứa một số nguyên âm $-1$, dòng thứ hai in ra số thứ tự của vị khách mà khách sạn không đáp ứng được nhu cầu thuê phòng.\n\n## Ví dụ\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3 \n2 5 4 3 \n2 1 3 \n3 2 4 \n4 2 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1 \n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n## Giải thích ví dụ\n- Sau khi khách hàng thứ $1$ thuê phòng, số lượng phòng còn lại trong $4$ ngày lần lượt là $0,3,2,3$. \n- Khách hàng thứ $2$ muốn thuê $3$ phòng từ ngày thứ $2$ đến ngày thứ $4$, nhưng số phòng còn trống vào ngày thứ $3$ chỉ còn $2$ phòng, do đó không thể thỏa mãn yêu cầu của người này.\n\n## Ràng buộc\n- Đối với 10% dữ liệu, có $1≤ n,m ≤ 10$;\n- Đối với 30% dữ liệu, có $1≤ n,m ≤ 1000$;\n- Đối với 70% dữ liệu, có $1 ≤ n,m ≤ 10^5$;\n- Đối với 100% dữ liệu, có $1 ≤ n,m ≤ 10^6,0 ≤ r_i,d_j ≤ 10^9,1 ≤ s_j ≤ t_j ≤ n$."}}]}