Snowy Smile
시간 제한3초메모리 제한512 MB
가중치가 있는 점 최대 2000개가 주어질 때, 경계를 포함해 사각형 안에 들어오는 점들의 가중치 합이 최대가 되는 축에 평행한 사각형을 찾는다. 빈 사각형도 허용한다.
문제
바이텔랜드에는 1, 2, . . . , n번이라는 번호가 붙은 n개의 해적 상자가 묻혀 있다. i번째 상자는 평면 위의 점 (xi, yi)에 있고, 그 가치는 wi이다. 해적이 상자 안에 독가스를 넣어 둘 수 있기 때문에 wi는 음수일 수 있다. i번째 해적 상자를 열면 wi만큼의 가치를 얻는다.
이 해적 상자들로 돈을 벌려고 한다. 변이 모두 좌표축에 평행한 직사각형을 하나 고른 뒤, 그 직사각형의 내부 또는 경계에 있는 모든 상자를 연다. 이때 값이 양수인지 음수인지와 상관없이 그 범위 안의 모든 상자를 반드시 열어야 한다. 하지만 아무것도 들어 있지 않은 직사각형을 골라 합이 0이 되게 할 수도 있다.
직사각형이 가질 수 있는 최대 총가치를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 테스트 케이스의 수를 나타내는 정수 T (1 ≤ T ≤ 100)가 주어진다.
각 테스트 케이스의 첫째 줄에는 해적 상자의 수를 나타내는 정수 n (1 ≤ n ≤ 2000)이 주어진다.
다음 n개 줄에는 각각 i번째 해적 상자를 나타내는 세 정수 xi, yi, wi (−109 ≤ xi, yi, wi ≤ 109)가 주어진다.
모든 테스트 케이스에서 n의 합은 10 000 이하이다.
출력
각 테스트 케이스마다 최대 총가치를 나타내는 정수 하나를 한 줄에 출력한다.