Bài tập

Điểm khác biệt giữa bản \(1\) và bản \(2\) là ở bản \(2\) có thêm sự xuất hiện của \(lim[i]\).

Sau một vụ đắm tàu bất ngờ trên đại dương, một đoàn thám hiểm nhỏ bị trôi dạt vào một hòn đảo kỳ lạ, nơi những tàn tích cổ đại lộ ra dưới ánh hoàng hôn. Không ai khác, họ đã vô tình đặt chân lên Atlantis huyền thoại --- thành phố từng được nhắc đến trong thần thoại cổ xưa.

Tuy nhiên, Atlantis không trồi lên vĩnh viễn. Theo những dấu tích cổ còn sót lại, họ nhận ra thành phố này sẽ lại chìm xuống biển sâu trong vòng \(d\) ngày tới. Thời gian không chờ đợi ai, và đoàn thám hiểm phải gấp rút thu thập càng nhiều thông tin, cổ vật và hiểu biết càng tốt trước khi Atlantis biến mất mãi mãi.

Thành phố có \(n\) khu vực khảo cổ. Mỗi khu vực ẩn chứa những cổ vật hoặc kiến thức có giá trị, nhưng việc khai quật và nghiên cứu không hề dễ dàng:

• Để tiếp cận và thu thập những thứ quan trọng ban đầu ở khu vực \(i\), đoàn thám hiểm cần dành ra \(p_i\) ngày.
• Sau khi đã tiếp cận được khu vực này, họ có thể tiếp tục đào sâu nghiên cứu về các hiện vật bên trong. Mỗi lần tìm hiểu thêm tốn \(t_i\) ngày và mang lại \(o_i\) điểm giá trị hữu ích.
• Mỗi khu vực chỉ cần khám phá ban đầu một lần, sau đó có thể tiếp tục khai thác sâu bao nhiêu lần tuỳ ý, nhưng mỗi khu vực có một giá trị \(lim_i\) là số lần khai thác tiếp còn đem lại giá trị. Nếu khai thác tại điểm \(i\) vượt quá số lần trên thì không đem lại giá trị.

Đoàn thám hiểm muốn biết: với tối đa \(d\) ngày trước khi Atlantis lại chìm xuống, họ có thể đạt được tổng giá trị hữu ích lớn nhất là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(d\) \((1 \leq n, d \leq 5000)\) --- số khu vực khảo cổ và số ngày còn lại trước khi Atlantis biến mất.
• Mỗi dòng trong số \(n\) dòng tiếp theo chứa ba số nguyên \(p_i,\ t_i,\ o_i,\ lim_i\) \((0 \leq p_i \leq 5000,\ 1 \leq t_i,\ lim_i \leq 5000,\ 1 \leq o_i \leq 10^9)\) --- thời gian thu thập ban đầu, thời gian cho mỗi lần nghiên cứu thêm, và giá trị hữu ích tương ứng.

Output

In ra một số nguyên --- giá trị hữu ích lớn nhất mà đoàn thám hiểm có thể đạt được trong \(d\) ngày.

Example

4 13
0 6 5 1
0 3 4 1
0 2 3 1
0 4 4 1

13

4 13
2 6 5 1
1 3 4 1
3 2 10 2
2 4 4 1

24

Scoring

\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 30 & \(n,\ d \le 100\)

2 & 70 & Không có ràng buộc bổ sung

\hline
\endtabular

Cho một số nguyên dương \(n\) có độ dài không quá \(10^5\).

Bạn có thể thực hiện thao tác sau vô số lần: chọn một chữ số trong số đó, bình phương nó, và thay chữ số cũ bằng kết quả (kết quả phải là một chữ số nghĩa là nếu chọn một chữ số \(x\) thì \(x^2 < 10\)).

Yêu cầu: Cho số nguyên dương \(n\). Có thể biến đổi để thu được một số chia hết cho \(9\) bằng những thao tác trên không?

Input

Vào từ file BIENDOI.INP:

• Dòng đầu tiên chứa số nguyên \(t\) -- là số lượng bộ truy vấn \((1 \le t \le 10^4)\).
• \(t\) dòng tiếp theo, mỗi dòng chứa số nguyên \(n\) \((1 \le |n| \le 10^5)\).

Dữ liệu đảm bảo rằng tổng độ dài của tất cả các số trong tất cả test không vượt quá \(10^5\).

Output

Ghi ra file BIENDOI.OUT: "YES" nếu có thể và "NO" nếu không.

Example

3
123
322
333333333333

NO
YES
YES

Ở một vùng đất xa xôi, nơi những con số có linh hồn riêng, một nhà giả kim số học tên Linh đã phát minh ra một trò chơi trí tuệ với tên gọi Hợp Nhất Vô Cực.

Linh tạo ra một bảng chứa \(N\) số nguyên dương, được viết thẳng hàng trên mặt phẳng ma thuật. Mỗi số trong bảng mang một nguồn năng lượng đặc biệt, và khi hai số giống nhau đứng cạnh nhau, Linh có thể kết hợp chúng thành một số mới, lớn hơn hai số ban đầu một đơn vị.

Sau khi kết hợp, hai viên đá cũ biến mất, và thay vào ngay điểm đó bằng viên đá mới. Mục tiêu của Linh là kết hợp sao cho, số lớn nhất trên các viên đá trên dãy là lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\) - số lượng các số trong bảng.
• Dòng thứ hai chứa \(N\) số nguyên dương, mỗi số không vượt quá \(40\) - các số trên bảng.

Output

• Ghi ra một số nguyên duy nhất - số lớn nhất có thể đạt được sau khi thực hiện các phép hợp nhất tối ưu.

Example

3
1 1 2

3

Scoring

• Với \(30\%\) số test, \(N \leq 1000\).
• Với \(70\%\) số test còn lại, không có ràng buộc gì thêm.

Cho ma trận \(n*n\), tính tổng các phần tử nằm trên các cột lẻ và hàng lẻ

Input

• Dòng 1: số \(n\) \((n < 100)\)

• Các dòng tiếp theo gồm các số mô tả bảng \(n*n\), giá trị tuyệt đối của các số không vượt quá 1000

Output

• In ra kết quả

Example

3
1 2 3
2 3 1
2 3 3

9