BOI 2024 - Ngày 1

Bạn đang điều hành một doanh nghiệp thành công, kiếm tiền bằng cách hoàn thành công việc cho khách hàng. Hiện có \(N\) công việc mà bạn có thể lựa chọn, được đánh số từ \(1\) đến \(N\). Mỗi công việc chỉ có thể thực hiện một lần.

Hoàn thành công việc \(i\) mang lại lợi nhuận \(x_i\) euro. Lợi nhuận cũng có thể âm, tức là \(x_i<0\).

Một số công việc phụ thuộc vào một công việc khác: có thể có công việc mang số hiệu \(p_i\) phải được hoàn thành trước khi bắt đầu công việc \(i\). Vì thế, một công việc có lợi nhuận lớn có thể không hấp dẫn như vẻ ngoài nếu nó phụ thuộc vào một công việc có lợi nhuận âm. Nếu \(p_i=0\), công việc \(i\) không phụ thuộc vào công việc nào.

Hiện bạn có \(s\) euro. Bạn được quyết định những công việc sẽ thực hiện và thứ tự thực hiện chúng, miễn là tuân thủ các quan hệ phụ thuộc. Ngoài ra, số tiền bạn có không được âm tại bất kỳ thời điểm nào.

Hãy tính lợi nhuận lớn nhất có thể thu được khi chọn thực hiện một số công việc trong \(N\) công việc theo một thứ tự do bạn quyết định. Bạn cũng có thể không thực hiện công việc nào.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(s\), lần lượt là số công việc và số tiền ban đầu bạn có.

Tiếp theo là \(N\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(p_i\), lần lượt là lợi nhuận và số hiệu công việc phải hoàn thành trước công việc \(i\). Nếu \(p_i=0\), công việc \(i\) không phụ thuộc vào công việc nào.

Dữ liệu ra

In ra một số nguyên duy nhất là lợi nhuận lớn nhất bạn có thể thu được.

Ràng buộc

• \(1\le N\le 3\cdot 10^5\).
• \(0\le s\le 10^{18}\).
• \(-10^9\le x_i\le 10^9\) với mọi \(1\le i\le N\).
• \(0\le p_i<i\) với mọi \(1\le i\le N\).

Phân nhóm

1. \(11\) điểm: \(s=10^{18}\).
2. \(14\) điểm: \(N\le 2000\) và với mọi \(1\le i\le N\), \(p_i=0\) hoặc \(p_i=i-1\).
3. \(15\) điểm: với mọi \(1\le i\le N\), \(p_i=0\) hoặc \(p_i=i-1\).
4. \(29\) điểm: \(N\le 2000\).
5. \(31\) điểm: không có ràng buộc bổ sung.

Ví dụ

6 1
3 0
-3 1
-5 0
2 1
6 3
-4 5

6

Bạn nghĩ rằng đặt người bạn thân của mình vào ô \((0,0)\) trên một lưới vô hạn gồm các ô được tô màu sẽ là một trò đùa thú vị. Người bạn sau đó di chuyển trên lưới mãi mãi, mỗi lần đi một bước sang một trong bốn ô kề cạnh.

Có \(N\) ô trên lưới chứa cổng dịch chuyển. Khi người bạn bước vào một ô có cổng, người ấy lập tức được dịch chuyển đến một cổng ngẫu nhiên, có thể là chính cổng vừa bước vào hoặc một cổng khác. Nếu ô \((0,0)\) có cổng, người bạn cũng được dịch chuyển ngay khi được đặt lên lưới lúc bắt đầu.

Bạn muốn đánh lừa để người bạn không nhận ra sự tồn tại của các cổng. Điều duy nhất người ấy nhìn thấy là màu của ô đang đứng, vì vậy bạn phải bảo đảm rằng, theo cảm nhận của người ấy, màu của các ô không bao giờ thay đổi. Cụ thể, nếu người ấy nghĩ rằng mình đã đi vào một ô nhiều lần, chẳng hạn bằng cách đi sang trái rồi lập tức đi sang phải, màu nhìn thấy phải giống như lần đầu tiên người ấy nghĩ rằng mình đã đi vào ô đó.

Lưu ý rằng khi bước vào một cổng, người bạn nhìn thấy cả màu của ô vừa bước vào lẫn màu của ô được dịch chuyển đến. Vì thế, bạn phải tô tất cả các ô có cổng cùng một màu để việc dịch chuyển không bị phát hiện ngay lập tức.

Một cách đơn giản là tô tất cả các ô cùng một màu. Nhưng màu sắc rất đẹp! Vì thế, bạn muốn dùng càng nhiều màu càng tốt.

Hãy tính số màu lớn nhất có thể dùng mà vẫn bảo đảm người bạn không nhận ra sự tồn tại của các cổng.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\) là số cổng dịch chuyển.

Tiếp theo là \(N\) dòng, mỗi dòng chứa hai số nguyên. Dòng thứ \(i\) chứa \(x_i\) và \(y_i\), cho biết có một cổng tại ô \((x_i,y_i)\).

Dữ liệu ra

In ra một số nguyên duy nhất là số màu lớn nhất có thể dùng mà người bạn không nhận ra các cổng, hoặc \(-1\) nếu có thể dùng vô hạn màu.

Ràng buộc

• \(1\le N\le 10^5\).
• \(-10^6\le x_i,y_i\le 10^6\) với mọi \(1\le i\le N\).
• Không có hai cổng có cùng tọa độ.

Phân nhóm

1. \(1\) điểm: \(N\le 2\).
2. \(10\) điểm: \(N\le 3\).
3. \(10\) điểm: với mọi số nguyên \(x_1,x_2,y_1,y_2\), nếu có cổng tại \((x_1,y_1)\) và \((x_2,y_2)\) thì cũng có cổng tại \((x_1,y_2)\).
4. \(29\) điểm: \(N\le 100\) và \(-100\le x_i,y_i\le 100\) với mọi \(1\le i\le N\).
5. \(15\) điểm: \(N\le 2000\).
6. \(35\) điểm: không có ràng buộc bổ sung.

Ví dụ

3
1 1
1 3
3 2

4

5
0 0
1 0
-1 0
0 1
0 -1

1

1
1 -1

-1

Bạn vừa đến Vilnius và muốn ghé thăm các thành phố khác nhau ở Litva.

Các thành phố ở Litva nằm trên một đường thẳng và được đánh số lần lượt từ \(1\) đến \(N\). Vilnius mang số \(1\).

Mỗi thành phố có một nhà ga với đúng một tuyến tàu xuất phát từ đó. Bạn chỉ có thể lên tàu ở ga đầu của tuyến, nhưng có thể xuống tại bất kỳ điểm dừng nào của tàu. Tàu xuất phát từ thành phố \(i\) dừng lại sau mỗi \(d_i\) thành phố và có \(x_i\) điểm dừng trên tuyến, không tính thành phố xuất phát. Nếu \(d_i=0\), tàu xuất phát từ thành phố \(i\) hiện không hoạt động và bạn không thể lên tàu đó.

Cụ thể, nếu lên tàu tại thành phố \(i\), bạn có thể xuống tại bất kỳ thành phố nào mang số \(i+t\cdot d_i\), với \(1\le t\le x_i\). Vì chỉ muốn ghé thăm các thành phố ở Litva, bạn sẽ không đi quá thành phố \(N\), ngay cả khi tuyến tàu còn những điểm dừng phía sau.

Bạn dự định ghé thăm một số thành phố và dùng tàu để di chuyển giữa chúng. Khi lập kế hoạch, bạn muốn biết có bao nhiêu hành trình khác nhau bắt đầu tại Vilnius. Hai hành trình khác nhau nếu dãy thành phố mà bạn dừng lại trong hai hành trình khác nhau.

Hãy tính số hành trình này và in ra kết quả lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\) là số thành phố.

Tiếp theo là \(N\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(d_i\) và \(x_i\) mô tả tuyến tàu xuất phát từ thành phố \(i\).

Dữ liệu ra

In ra một số nguyên duy nhất là số cách ghé thăm một số trong \(N\) thành phố, lấy modulo \(10^9+7\).

Ràng buộc

• \(1\le N\le 10^5\).
• \(0\le d_i\le 10^9\) với mọi \(1\le i\le N\).
• \(0\le x_i\le 10^9\) với mọi \(1\le i\le N\).

Phân nhóm

1. \(8\) điểm: \(N\le 15\).
2. \(13\) điểm: \(N\le 10^4\).
3. \(16\) điểm: \(d_i=1\) với mọi \(1\le i\le N\).
4. \(34\) điểm: \(x_i=10^9\) với mọi \(1\le i\le N\).
5. \(29\) điểm: không có ràng buộc bổ sung.

Ví dụ

5
1 3
2 1
1 3
0 10
3 5

7