Xếp gạch

Xem PDF

Điểm: 500 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho \(N\) viên gạch hình chữ nhật có kích thước là \(a_i, b_i, h_i\) lần lượt là chiều dài, chiều rộng, chiều cao của viên gạch thứ \(i\).

Tìm cách xếp các khối gạch thành 1 tháp. Sao cho các cạnh của các viên gạch song song với nhau và hình chữ nhật ở phía trên nằm trọn trong hình chữ nhật phía dưới.

Viên gạch thứ \(j\) có thể nằm trên viên gạch thứ \(i\) khi \(a_i>a_j\)\(b_i>b_j\)

Tìm số viên gạch tối đa có thể chồng lên nhau và chiều cao tối đa của tháp.

Input

  • Dòng đầu tiên chứa một số nguyên dương \(N\) (\(n\le 5000\)) là số viên gạch
  • \(N\) dòng tiếp theo mỗi dòng chứa 3 số \(a_i, b_i, h_i\).

Output

  • Gồm 2 số \(x,y\) lần lượt là số viên gạch tối đa trong 1 tháp và chiều cao tối đa của tháp dựng tự các viên gạch

Example

Test 1

Input
10
9 7 1
10 4 8
8 5 5
7 4 10
7 4 8
5 1 9
2 1 10
3 2 4
5 4 5
10 3 2 
Output
5 30

Bình luận