{"trustable":true,"sections":[{"title":"Mô tả","value":{"format":"MD","content":"Ở trường đại học, mỗi sinh viên cần chọn một số môn học từ nhiều môn học để đạt được một số tín chỉ nhất định. Trong các môn học, có những môn học mà phải học trước một số môn học khác, ví dụ như môn toán cao cấp luôn phải học trước các môn học khác. Bây giờ có $N$ môn học, mỗi môn có một số tín chỉ, mỗi môn có một môn học trực tiếp tiên quyết hoặc không (nếu môn học a là môn học tiên quyết của môn học b thì chỉ khi học xong môn học a, mới có thể học môn học b). Một sinh viên cần chọn $M$ môn học từ những môn học này để học, hỏi anh ta có thể đạt được tối đa bao nhiêu tín chỉ?"}},{"title":"Nhập","value":{"format":"MD","content":"Dòng đầu tiên chứa hai số nguyên $N$ , $M$ cách nhau bởi dấu cách. ( $1 \\leq N \\leq 300$ , $1 \\leq M \\leq 300$ )\n\nTiếp theo là $N$ dòng, dòng thứ $I+1$ chứa hai số nguyên $k_i $ và $s_i$, $k_i$ biểu thị môn học thứ I có môn học tiên quyết, $s_i$ biểu thị số tín chỉ của môn học đó. Nếu $k_i\u003d0$ biểu thị không có môn học tiên quyết ( $1 \\leq {k_i} \\leq N$ , $1 \\leq {s_i} \\leq 20$ )."}},{"title":"Xuất","value":{"format":"MD","content":"Chỉ có một dòng, số tín chỉ tối đa khi chọn $M$ môn học."}},{"title":"Ví dụ 1","value":{"format":"MD","content":"\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\u003e7 4\n2 2\n0 1\n0 4\n2 1\n7 1\n7 6\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}