시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB255825530.055%

문제

외계인들이 지구를 침략했다. (결국!) 스스로를 방어하지 않으면 죽는다! 아니면 동화되거나. 먹힐 수도 있다. 사실 잘 모르겠다.

외계인들은 다음과 같은 공격 패턴을 따른다. n명의 외계인이 있고, i번 외계인은 di 만큼 떨어진 곳에서 ai 시간에 나타난다. 이 외계인은 bi 시간에 당신을 공격할 것이다. 따라서 정확히 bi 시간 또는 그 이전에 처치해야 한다.

당신의 무기는 광자폭탄으로, 폭발력을 마음대로 조절할 수 있다. 만약 폭발력을 R로 설정하고 터뜨렸다면, 거리 R 이하의 모든 외계인이 즉사한다. 그리고 R 만큼의 연료를 소모한다.

공격당하지 않고 모든 외계인을 처치하는 데 필요한 최소 연료의 양을 구하여라.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 첫 줄에 외계인의 수 n (1 ≤ n ≤ 300)이 주어지고, 다음 n 줄에 ai, bi, di (1 ≤ ai < bi ≤ 10 000; 1 ≤ di ≤ 10 000)가 주어진다.

출력

각 테스트 케이스마다, 한 줄에 모든 외계인을 처치하는 데 필요한 최소 연료의 양을 출력한다.

예제 입력 1

1
3
1 4 4
4 7 5
3 4 7

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjEwNTEzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNjc4XHVhY2M0IFx1Y2U2OFx1YjdiNVx1Yzc5MCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNjc4XHVhY2M0XHVjNzc4XHViNGU0XHVjNzc0IFx1YzljMFx1YWQ2Y1x1Yjk3YyBcdWNlNjhcdWI3YjVcdWQ1ODhcdWIyZTQuIChcdWFjYjBcdWFkNmQhKSBcdWMyYTRcdWMyYTRcdWI4NWNcdWI5N2MgXHViYzI5XHVjNWI0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBcdWM4ZmRcdWIyOTRcdWIyZTQhIFx1YzU0NFx1YjJjOFx1YmE3NCBcdWIzZDlcdWQ2NTRcdWI0MThcdWFjNzBcdWIwOTguIFx1YmEzOVx1ZDc5MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWMwYWNcdWMyZTQgXHVjNzk4IFx1YmFhOFx1Yjk3NFx1YWNhMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjc4XHVhY2M0XHVjNzc4XHViNGU0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhY2Y1XHVhY2E5IFx1ZDMyOFx1ZDEzNFx1Yzc0NCBcdWI1MzBcdWI5NzhcdWIyZTQuIG5cdWJhODVcdWM3NTggXHVjNjc4XHVhY2M0XHVjNzc4XHVjNzc0IFx1Yzc4OFx1YWNlMCwgaVx1YmM4OCBcdWM2NzhcdWFjYzRcdWM3NzhcdWM3NDAgZDxzdWI+aTxcL3N1Yj4gXHViOWNjXHVkMDdjIFx1YjVhOFx1YzViNFx1YzljNCBcdWFjZjNcdWM1ZDBcdWMxMWMgYTxzdWI+aTxcL3N1Yj4gXHVjMmRjXHVhYzA0XHVjNWQwIFx1YjA5OFx1ZDBjMFx1YjA5Y1x1YjJlNC4gXHVjNzc0IFx1YzY3OFx1YWNjNFx1Yzc3OFx1Yzc0MCBiPHN1Yj5pPFwvc3ViPiBcdWMyZGNcdWFjMDRcdWM1ZDAgXHViMmY5XHVjMmUwXHVjNzQ0IFx1YWNmNVx1YWNhOVx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM4MTVcdWQ2NTVcdWQ3ODggYjxzdWI+aTxcL3N1Yj4gXHVjMmRjXHVhYzA0IFx1YjYxMFx1YjI5NCBcdWFkZjggXHVjNzc0XHVjODA0XHVjNWQwIFx1Y2M5OFx1Y2U1OFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc1OCBcdWJiMzRcdWFlMzBcdWIyOTQgXHVhZDExXHVjNzkwXHVkM2VkXHVkMGM0XHVjNzNjXHViODVjLCBcdWQzZWRcdWJjMWNcdWI4MjVcdWM3NDQgXHViOWM4XHVjNzRjXHViMzAwXHViODVjIFx1Yzg3MFx1YzgwOFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVkM2VkXHViYzFjXHViODI1XHVjNzQ0IFJcdWI4NWMgXHVjMTI0XHVjODE1XHVkNTU4XHVhY2UwIFx1ZDEzMFx1YjcyOFx1YjgzOFx1YjJlNFx1YmE3NCwgXHVhYzcwXHViOWFjIFIgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM2NzhcdWFjYzRcdWM3NzhcdWM3NzQgXHVjOTg5XHVjMGFjXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgUiBcdWI5Y2NcdWQwN2NcdWM3NTggXHVjNWYwXHViOGNjXHViOTdjIFx1YzE4Y1x1YmFhOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2Y1XHVhY2E5XHViMmY5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWJhYThcdWI0ZTAgXHVjNjc4XHVhY2M0XHVjNzc4XHVjNzQ0IFx1Y2M5OFx1Y2U1OFx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWM1ZjBcdWI4Y2NcdWM3NTggXHVjNTkxXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzY3OFx1YWNjNFx1Yzc3OFx1Yzc1OCBcdWMyMTggbiAoMSAmbGU7IG4gJmxlOyAzMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHViMmU0XHVjNzRjIG4gXHVjOTA0XHVjNWQwIGFpLCBiaSwgZGkgKDEgJmxlOyBhaSAmbHQ7IGJpICZsZTsgMTAgMDAwOyAxICZsZTsgZGkgJmxlOyAxMCAwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWJhYThcdWI0ZTAgXHVjNjc4XHVhY2M0XHVjNzc4XHVjNzQ0IFx1Y2M5OFx1Y2U1OFx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWM1ZjBcdWI4Y2NcdWM3NTggXHVjNTkxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDUxMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik91dGVyIHNwYWNlIGludmFkZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgYWxpZW5zIGZyb20gb3V0ZXIgc3BhY2UgaGF2ZSAoZmluYWxseSEpIGludmFkZWQgRWFydGguIERlZmVuZCB5b3Vyc2VsZiwgb3IgYmUgZGlzaW50ZWdyYXRlZCEgT3IgYXNzaW1pbGF0ZWQuIE9yIGVhdGVuLiBXZSBhcmUgbm90IHlldCBzdXJlLjxcL3A+XHJcblxyXG48cD5UaGUgYWxpZW5zIGZvbGxvdyBhIGtub3duIGF0dGFjayBwYXR0ZXJuLiBUaGVyZSBhcmUgbiBhdHRhY2tlcnMsIHRoZSBpLXRoIG9uZSBhcHBlYXJzIGF0IHRpbWUgYTxzdWI+aTxcL3N1Yj4sIGF0IGRpc3RhbmNlIGQ8c3ViPmk8XC9zdWI+IGZyb20geW91LiBIZSBtdXN0IGJlIGRlc3Ryb3llZCBubyBsYXRlciB0aGFuIGF0IHRpbWUgYjxzdWI+aTxcL3N1Yj4sIG9yIGVsc2UgaGUgd2lsbCBmaXJlIGhpcyB3ZWFwb24sIHdoaWNoIHdpbGwgZGVmaW5pdGVseSBlbmQgdGhlIGZpZ2h0LjxcL3A+XHJcblxyXG48cD5Zb3VyIHdlYXBvbiBpcyBhbiBhcmVhLWJsYXN0ZXIsIHdoaWNoIGNhbiBiZSBzZXQgdG8gYW55IGdpdmVuIHBvd2VyLiBJZiBmaXJlZCB3aXRoIHBvd2VyIFIsIGl0IG1vbWVudGFyaWx5IGRlc3Ryb3lzIGFsbCBhbGllbnMgYXQgZGlzdGFuY2UgUiBvciBzbWFsbGVyLiBJdCBhbHNvIGNvbnN1bWVzIFIgZnVlbCBjZWxscy48XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHRoZSBtaW5pbWFsIGNvc3QgKG1lYXN1cmVkIGluIGZ1ZWwgY2VsbHMpIG9mIGRlc3Ryb3lpbmcgYWxsIHRoZSBhbGllbnMsIHdpdGhvdXQgYmVpbmcga2lsbGVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQuIFRoZSBkZXNjcmlwdGlvbnMgb2YgdGhlIHRlc3QgY2FzZXMgZm9sbG93OjxcL3A+XHJcblxyXG48cD5FYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIGFsaWVucyBuICgxICZsZTsgbiAmbGU7IDMwMCkuIE9mIHRoZSBuZXh0IG4gbGluZXMsIHRoZSBpLXRoIG9uZSBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4sIGQ8c3ViPmk8XC9zdWI+LCAoMSAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsdDsgYjxzdWI+aTxcL3N1Yj4gJmxlOyAxMCAwMDA7IDEgJmxlOyBkPHN1Yj5pPFwvc3ViPiAmbGU7IDEwIDAwMCkuIFRoZSBpLXRoIGFsaWVuIGFwcGVhcnMgYXQgdGltZSBhPHN1Yj5pPFwvc3ViPiwgaXMgaWRsZSB1bnRpbCBiPHN1Yj5pPFwvc3ViPiwgYW5kIGhpcyBkaXN0YW5jZSBmcm9tIHlvdSBpcyBkPHN1Yj5pPFwvc3ViPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIHRoZSBtaW5pbXVtIG51bWJlciBvZiBjZWxscyBuZWVkZWQgdG8gZGVzdHJveSBhbGwgdGhlIGFsaWVucy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d