Read candidate records, sort them by decreasing salary, and compute the total salary.

Input

The first line contains \(n\). For each candidate, three following lines contain the identifier, full name, and salary; blank separator lines may occur.

The input satisfies:

• \(0 <= n <= 10\)

Output

Print the legacy prompts, the records in decreasing salary order, and Total Salary: S, exactly as shown in the example.

Example

Input

3
uv1
Le Nguyen Hoang Long
2000

uv2
Luong Nguyen Minh Ngoc
1000

uv3
Nguyen Thi Bich Ngoc
5000

Output

n = So nguoi ung tuyen = 3
Nhap thong tin ung vien thu 1:
id: Name: Salary: Nhap thong tin ung vien thu 2:
id: Name: Salary: Nhap thong tin ung vien thu 3:
id: Name: Salary: uv3 Nguyen Thi Bich Ngoc 5000
uv1 Le Nguyen Hoang Long  2000
uv2 Luong Nguyen Minh Ngoc 1000
Total Salary: 8000