Quy hoạch động

Cho một lưới ô vuông \(A\) kích thước \(m×n\), các hàng của lưới được đánh số từ \(1\) tới \(m\) từ trên xuống dưới, các cột của lưới được đánh số từ \(1\) tới \(n\) từ trái qua phải, trên mỗi ô của lưới ghi một số nguyên.
Người ta muốn tìm một cách đi từ cột \(1\) tới cột \(n\) của lưới theo quy tắc: từ một ô chỉ được phép đi sang một trong các ô ở cột bên phải có đỉnh chung với ô đang đứng (không đi ra ngoài lưới).
Hãy chỉ ra một cách đi mà tổng các số ghi trên các ô đi qua là lớn nhất.

Input

• Dòng đầu gồm 2 số nguyên dương \(m,n \leq 1000\) .
• \(m\) dòng tiếp theo, mỗi dòng là \(n\) số nguyên có giá trị tuyệt đối không vượt quá \(10^6\), số thứ \(j\) là số ghi trên ô \((i,j)\) của lưới.

Output

• Dòng 1 : Ghi tổng các số ghi trên các ô đi qua trên đường đi tìm được.
• \(n\) dòng tiếp theo mỗi dòng ghi chỉ số hàng và chỉ số cột của một ô đi qua theo đúng thứ tự trên hành trình tìm được.

Example

4 5
7 2 1 2 6
1 2 5 4 5
1 5 3 5 2
5 2 3 1 1

25
4 1
3 2
2 3
2 4
1 5

Nước Silverland sử dụng hệ thống \(100\) loại tiền xu, trong đó các xu có mệnh giá là một số chính phương từ \(1^2\) đến \(100^2\):
Với hệ thống này, để trả chính xác \(10\) xu ta có \(4\) cách:

• Trả \(10\) đồng \(1\) xu.
• Trả \(6\) đồng \(1\) xu và \(1\) đồng \(4\) xu.
• Trả \(2\) đồng \(1\) xu và \(2\) đồng \(4\) xu.
• Trả \(1\) đồng \(1\) xu và \(1\) đồng \(9\) xu.

Hãy xác định số lượng cách trả chính xác một số tiền \(m\) cho trước ở Silverland và đưa ra một cách trả phải dùng ít đồng xu nhất.

Input

• Dòng 1: số nguyên dương \(m\) \((m≤10^5 )\).

Output

• Dòng 1 : số nguyên \(k\) là số lượng cách trả, lấy phần dư khi chia cho 123456789;
• Dòng 2: số nguyên \(q\) là số đồng xu tối thiểu phải sử dụng để trả;
• Các dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(a,b\) cho biết sử dụng \(a\) đồng xu loại mệnh giá \(b^2\) trong phương án tối ưu (dùng ít đồng xu nhất).

Example

19

10
3
2 3
1 1

Dạo này, shiba có thói quen thích nghe nhạc. Cậu ấy quyết định mua một máy nghe nhạc (loại cũ) để thử cảm giác nghe nhạc của cuối những thập niên 90 :Đ.

Có tất cả \(n\) bài nhạc, bài nhạc thứ \(i\) dài đúng \(a_{i}\) phút. Máy nghe nhạc mà shiba mua ghi được tối đa \(m\) phút. Hỏi có bao nhiêu cách ghi nhạc khác nhau lên máy nghe nhạc, biết rằng mỗi bài nhạc chỉ được phép ghi một lần lên máy?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,m\) (\(n \le 1000, m \le 1000\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{i}\) (\(a_{i} \le 1000\)).

Output

• Một số nguyên duy nhất là cách ghi nhạc lên máy nghe nhạc mà shiba có thể thực hiện, lấy phần dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 6\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 20\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3 4
1 5 6

1

Do chán không có gì làm, Đức và Thái cùng nhau ngồi lắp một chiếc đồng hồ kiểu độc lạ Bình Dương.

Đồng hồ bình thường gồm \(3\) chiếc bánh răng, một chiếc quản lí kim giờ, một chiếc quản lí kim phút, một chiếc quản lí kim giây. Bánh răng có \(t\) răng thì có thể biểu hiện \(t\) trạng thái. Chi phí để mua một chiếc bánh răng có \(t\) răng là \(t\) đồng. Dựa trên cấu trúc đó, Đức và Thái muốn lắp một chiếc đồng hồ có số lượng bánh răng tùy ý, sử dụng các loại bánh răng tùy ý sao cho số lượng trạng thái là TỐI ĐA. Nếu một chiếc đồng hồ có \(n\) bánh răng, số lượng răng lần lượt là \(t_1,t_2,...,t_n\) thì số lượng trạng thái có thể được tính bằng công thức \(LCM(t_1,t_2,...,t_n)\) (bội chung nhỏ nhất của các số nguyên \(t_1,t_2,...,t_n\)).

Do chỉ là một trò tiêu khiển giải trí, số tiền mà hai người có thể chi ra cho chiếc đồng hồ là \(b\) đồng. Bạn hãy giúp tìm số lượng trạng thái TỐI ĐA của mỗi chiếc đồng hồ với chi phí bị giới hạn.

Do kết quả có thể rất lớn, bạn cần đưa ra kết quả theo Logarit Tự nhiên (Logarit cơ số \(e = 2.718281828459...\)).

Cho biết:

• Kí hiệu Logarit Tự nhiên của một số tự nhiên \(N\) là \(ln(N)\).
• \(ln(a \times b) = ln(a) + ln(b)\).

Input

• Dòng thứ nhất chứa một số nguyên dương \(\phi\) - mô tả subtask của test.
• Dòng thứ hai là một số nguyên dương \(T\) (\(1 \le T \le 30000\)) - số bộ dữ liệu.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(b\) (\(1 \le b \le 30000\)).

Output

• Với mỗi bộ dữ liệu, đưa ra kết quả trên một dòng. Kết quả của bạn sẽ được chấp nhận nếu sai số tuyệt đối hoặc tương đối so với kết quả không vượt quá \(10^{-6}\).

Scoring

• Subtask \(1\) (\(8\%\) số điểm): \(T = 1, b \le 8\).
• Subtask \(2\) (\(15\%\) số điểm): \(b \le 8\).
• Subtask \(3\) (\(20\%\) số điểm): \(b \le 17\).
• Subtask \(4\) (\(27\%\) số điểm): \(b \le 1000\).
• Subtask \(5\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

2
2
2
7

0.693147181
2.484906650