Bài tập

Bác Sắn có \(N\) chiếc bình gốm cổ được xếp thẳng hàng trong một chiếc hộp dài mở hai đầu, bình thứ \(i\) có giá trị gốc \(v_i\). Mỗi ngày bác chỉ bán được một bình và chỉ được lấy bình ở đầu trái hoặc đầu phải của hàng bình còn lại.

Bình càng để lâu càng quý: nếu bình có giá trị gốc \(v\) được bán vào ngày thứ \(a\) (ngày đầu tiên là \(a = 1\)) thì bác thu được \(v \cdot a\) đồng.

Hãy tìm cách bán hết \(N\) bình để tổng số tiền thu được là lớn nhất, và in ra số tiền đó.

Input

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(v_1, v_2, \dots, v_N\) theo thứ tự xếp trong hộp.

Output

In ra một số nguyên là tổng tiền lớn nhất có thể thu được.

Constraints

• \(1 \le N \le 2000\)
• \(1 \le v_i \le 1000\)

Sample Input

6
2 7 3 1 9 4

Sample Output

103

Explanation

Cách bán tối ưu: lấy bình ở đầu trái bốn lần, rồi lấy hai bình ở đầu phải. Thứ tự bán là \(2, 7, 3, 1, 4, 9\) vào các ngày \(1, \dots, 6\): \(2\cdot1 + 7\cdot2 + 3\cdot3 + 1\cdot4 + 4\cdot5 + 9\cdot6 = 103\).

Cho danh sách điểm môn Tin học của một lớp. Mỗi điểm là số thực từ \(0.0\) đến \(10.0\) và được viết với đúng một chữ số thập phân. Hãy liệt kê ba điểm cao nhất theo thứ tự giảm dần. Nếu có nhiều bạn cùng điểm thì mỗi bạn được tính riêng (ví dụ danh sách \(10.0\ 10.0\ 9.9\) cho ra ba điểm \(10.0\ 10.0\ 9.9\)).

Input

Một dòng duy nhất chứa danh sách điểm, các điểm cách nhau bởi một hoặc nhiều dấu cách. Danh sách có ít nhất \(3\) điểm.

Output

In ra ba điểm cao nhất theo thứ tự giảm dần, cách nhau một dấu cách, mỗi điểm có đúng một chữ số thập phân.

Constraints

• Danh sách có từ \(3\) đến \(1000\) điểm.

Sample Input

7.5 9.5 6.0 8.5 9.0 5.5

Sample Output

9.5 9.0 8.5

Một cái hồ có mặt hồ hình chữ nhật kích thước \(a \times b\) (mét), ban đầu hồ cạn. Máy bơm có công suất cố định \(3\ m^3\) mỗi giờ và được bật liên tục trong \(t\) giờ (không có nước chảy đi nơi khác). Một em bé rơi xuống hồ có chiều cao tính đến cổ là \(k\) (cm). Em bé được coi là an toàn nếu mực nước trong hồ không vượt quá \(k\) cm.

Hãy cho biết em bé có an toàn hay không.

Input

• Một dòng gồm bốn số nguyên dương \(a, b, k, t\), cách nhau bởi dấu cách.

Output

• In YES nếu em bé an toàn, ngược lại in WARNING.

Constraints

• \(1 \le a, b, k, t \le 9999\)

Sample Input 1

5 4 60 2

Sample Output 1

YES

Sample Input 2

6 5 20 4

Sample Output 2

WARNING

Explanation

Ở ví dụ 1, lượng nước là \(6\ m^3\) trên diện tích \(20\ m^2\), mực nước \(0.3\ m = 30\) cm \(\le 60\) cm nên an toàn. Ở ví dụ 2, lượng nước \(12\ m^3\) trên diện tích \(30\ m^2\), mực nước \(40\) cm \(> 20\) cm nên nguy hiểm.

Một nhà thám hiểm muốn ghé thăm đủ \(N\) thành phố, được đánh số từ \(1\) đến \(N\), bằng đường hàng không. Anh ta được tự do chọn thành phố xuất phát, sau đó bay lần lượt qua các thành phố còn lại sao cho mỗi thành phố được ghé đúng một lần (không cần quay về điểm đầu).

Giá vé bay thẳng từ thành phố \(i\) đến thành phố \(j\) là \(c_{i,j}\) (giá vé chiều đi và chiều về có thể khác nhau). Trong bài này, hãy chỉ ra một hành trình có tổng tiền vé nhỏ nhất.

Nếu có nhiều hành trình cùng có tổng tiền vé nhỏ nhất, hãy in hành trình có thứ tự từ điển nhỏ nhất (so sánh dãy các thành phố theo thứ tự ghé thăm, tại vị trí đầu tiên khác nhau, dãy có số nhỏ hơn được coi là nhỏ hơn).

Input

• Dòng đầu chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(N\) số nguyên \(c_{i,1}, c_{i,2}, \dots, c_{i,N}\).

Output

In ra \(N\) số nguyên trên một dòng, cách nhau một dấu cách: các thành phố theo thứ tự được ghé thăm.

Constraints

• \(1 \le N \le 16\).
• \(c_{i,i} = 0\); với \(i \ne j\) thì \(1 \le c_{i,j} \le 10^9\).

Sample Input

5
0 2 9 4 6
3 0 1 7 2
8 5 0 3 1
2 6 4 0 5
7 1 3 2 0

Sample Output

1 2 3 5 4

Explanation

Hành trình \(1 \to 2 \to 3 \to 5 \to 4\) có tổng chi phí \(2 + 1 + 1 + 2 = 6\), đây là mức nhỏ nhất và là hành trình nhỏ nhất theo thứ tự từ điển trong các hành trình tối ưu.