Tại kỳ thi Olympic Tin học toàn Nga năm 2224, được tổ chức ở Иннополис, việc giao hàng do các rô-bốt thế hệ mới có khả năng tạo ra bản sao của chính mình đảm nhiệm. Người nhận có thể nhận hàng ngay qua cửa sổ mà không cần ra khỏi nhà.
Ban đầu chỉ có một rô-bốt giao hàng. Vào bất kỳ thời điểm nào, rô-bốt trên cùng có thể tạo ra một hoặc nhiều rô-bốt mới ngay phía trên mình. Nhờ đó hình thành một cột rô-bốt. Chiều cao của mỗi rô-bốt bằng chiều cao của một tầng nhà.
Trong quá trình giao hàng, cột các rô-bốt bản sao giống nhau di chuyển dọc theo các tòa nhà ký túc xá từ trái sang phải. Cơ sở dữ liệu của các rô-bốt chứa danh sách những đơn hàng đã đặt; với mỗi đơn hàng, cửa sổ cần giao đến đã được biết. Khi cột rô-bốt đi ngang qua cửa sổ tương ứng với một đơn hàng, nó có thể giao hàng nếu trong cột có một rô-bốt ở ngang độ cao của cửa sổ.
Trong lúc di chuyển, cột rô-bốt có thể gặp chướng ngại vật. Sau chướng ngại vật, chỉ những rô-bốt trước đó nằm cao hơn chướng ngại vật mới tiếp tục di chuyển. Chúng nằm trên mặt đất ngay phía sau chướng ngại vật, vẫn xếp thành một cột thẳng đứng, và có thể tiếp tục di chuyển, tạo thêm bản sao và giao các đơn hàng.
Khoảng cách giữa các chướng ngại vật và cửa sổ đủ lớn nên trong lúc vượt qua chướng ngại vật, các rô-bốt sẽ không đi ngang qua cửa sổ nào.
Với mỗi đơn hàng được giao, công ty tổ chức giao hàng nhận được $p$ rúp tiền mã hóa. Chi phí tạo một rô-bốt mới là $c$ rúp tiền mã hóa. Lợi nhuận cuối cùng bằng tổng doanh thu từ việc giao hàng trừ đi tổng chi phí tạo tất cả các rô-bốt. Công ty muốn tối đa hóa lợi nhuận. Công ty không bắt buộc phải giao mọi đơn hàng, và các rô-bốt có thể dừng lại và kết thúc quá trình giao hàng bất cứ lúc nào.
Hãy xác định lợi nhuận lớn nhất mà công ty có thể thu được.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa bốn số nguyên $n$, $m$, $c$, $p$ ($0 \le n,m \le 100000$, $1 \le c,p \le 10^6$) — lần lượt là số chướng ngại vật, số đơn hàng trong cơ sở dữ liệu, chi phí tạo một bản sao rô-bốt và tiền thu được khi giao một đơn hàng.
Trong $n+m$ dòng tiếp theo là mô tả các chướng ngại vật và cửa sổ cần giao hàng đến, theo thứ tự cột rô-bốt gặp chúng khi di chuyển dọc ký túc xá từ trái sang phải. Mỗi dòng chứa hai số nguyên $t_i$ và $h_i$ ($1 \le t_i \le 2$, $1 \le h_i \le 10^6$) — loại đối tượng $t_i$ ($1$ là chướng ngại vật và $2$ là cửa sổ), và $h_i$ là chiều cao của chướng ngại vật tính theo số tầng hoặc tầng có cửa sổ.
Bảo đảm có đúng $n$ đối tượng loại $1$, và $m$ đối tượng còn lại có loại $2$.
Dữ liệu ra
In ra một số — lợi nhuận lớn nhất có thể thu được.
Nhiệm vụ con
| Nhiệm vụ con | Điểm | Giới hạn: $n$ | Giới hạn: $m$ | Giới hạn bổ sung | Nhiệm vụ con cần thiết |
|---|---|---|---|---|---|
| 1 | 24 | $n \le 100$ | $m \le 100$ | $h_i \le 100$ | |
| 2 | 12 | $n=0$ | |||
| 3 | 14 | $n=1$ | |||
| 4 | 15 | $m=1$ | |||
| 5 | 17 | $c=1$, $p=10^6$; chiều cao của mọi chướng ngại vật đều bằng $1$ | |||
| 6 | 18 | Ví dụ, 1–5 |
Ví dụ
Dữ liệu vào 1
2 3 2 6 1 2 2 3 1 1 2 6 2 2
Dữ liệu ra 1
4
Dữ liệu vào 2
1 3 1 5 2 2 2 1 1 9 2 1
Dữ liệu ra 2
9
Ghi chú
Một trong những chiến lược giao các đơn hàng tối ưu của ví dụ thứ nhất được minh họa trong chín hình dưới đây; việc giao đơn hàng thứ hai không làm tăng lợi nhuận.
Trong ví dụ thứ hai, chỉ cần sao chép rô-bốt một lần để giao đơn hàng đầu tiên, dùng hệ rô-bốt thu được để giao đơn hàng thứ hai; việc tạo thêm bản sao để giao đơn hàng thứ ba không có lợi về mặt kinh tế.