시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB38931991163251.678%

문제

상근이는 트럭을 가지고 긴 일직선 도로를 운전하고 있다. 도로에는 신호등이 설치되어 있다. 상근이는 각 신호등에 대해서 빨간 불이 지속되는 시간과 초록 불이 지속되는 시간을 미리 구해왔다. (빨강색과 초록색 불빛은 무한히 반복된다)

상근이의 트럭이 도로에 진입했을 때, 모든 신호등의 색상은 빨간색이고, 사이클이 막 시작한 상태이다. 상근이는 1초에 1미터를 움직인다. 신호등의 색상이 빨간색인 경우에는 그 자리에서 멈추고 초록색으로 바뀔때 까지 기다린다.

상근이가 도로의 끝까지 이동하는데 걸리는 시간을 구하는 프로그램을 작성하시오. 도로의 시작은 0미터이고, 끝은 L미터인 지점이다.

입력

첫째 줄에 신호등의 개수 N과 도로의 길이 L이 주어진다. (1 ≤ N ≤ 100, 1 ≤ L ≤ 1000)

다음 N개 줄에는 각 신호등의 정보 D, R, G가 주어진다. (1 ≤ D < L, 1 ≤ R ≤ 100, 1 ≤ G ≤ 100) D는 신호등의 위치이며, R과 G는 빨간색, 초록색이 지속되는 시간이다.

신호등은 D가 증가하는 순서로 주어지며, 같은 위치에 있는 신호등이 두 개 이상 있는 경우는 없다.

출력

첫째 줄에 상근이가 도로의 끝까지 이동하는데 걸리는 시간을 출력한다.

예제 입력 1

2 10
3 5 5
5 2 2

예제 출력 1

12

예제 입력 2

4 30
7 13 5
14 4 4
15 3 10
25 1 1

예제 출력 2

36
W3sicHJvYmxlbV9pZCI6IjI5ODAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWI4NWNcdWM2NDAgXHVjMmUwXHVkNjM4XHViNGYxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkMmI4XHViN2VkXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWFlMzQgXHVjNzdjXHVjOWMxXHVjMTIwIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM2YjRcdWM4MDRcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWIzYzRcdWI4NWNcdWM1ZDBcdWIyOTQgXHVjMmUwXHVkNjM4XHViNGYxXHVjNzc0IFx1YzEyNFx1Y2U1OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDEgXHVjMmUwXHVkNjM4XHViNGYxXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWJlNjhcdWFjMDQgXHViZDg4XHVjNzc0IFx1YzljMFx1YzE4ZFx1YjQxOFx1YjI5NCBcdWMyZGNcdWFjMDRcdWFjZmMgXHVjZDA4XHViODVkIFx1YmQ4OFx1Yzc3NCBcdWM5YzBcdWMxOGRcdWI0MThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YmJmOFx1YjlhYyBcdWFkNmNcdWQ1NzRcdWM2NTRcdWIyZTQuIChcdWJlNjhcdWFjMTVcdWMwYzlcdWFjZmMgXHVjZDA4XHViODVkXHVjMGM5IFx1YmQ4OFx1YmU1Ylx1Yzc0MCBcdWJiMzRcdWQ1NWNcdWQ3ODggXHViYzE4XHViY2Y1XHViNDFjXHViMmU0KTxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVkMmI4XHViN2VkXHVjNzc0IFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWM5YzRcdWM3ODVcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVjMmUwXHVkNjM4XHViNGYxXHVjNzU4IFx1YzBjOVx1YzBjMVx1Yzc0MCBcdWJlNjhcdWFjMDRcdWMwYzlcdWM3NzRcdWFjZTAsIFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWI5YzkgXHVjMmRjXHVjNzkxXHVkNTVjIFx1YzBjMVx1ZDBkY1x1Yzc3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IDFcdWNkMDhcdWM1ZDAgMVx1YmJmOFx1ZDEzMFx1Yjk3YyBcdWM2YzBcdWM5YzFcdWM3NzhcdWIyZTQuIFx1YzJlMFx1ZDYzOFx1YjRmMVx1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NzQgXHViZTY4XHVhYzA0XHVjMGM5XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwXHVjMTFjIFx1YmE0OFx1Y2Q5NFx1YWNlMCBcdWNkMDhcdWI4NWRcdWMwYzlcdWM3M2NcdWI4NWMgXHViYzE0XHViMDE0XHViNTRjIFx1YWU0Y1x1YzljMCBcdWFlMzBcdWIyZTRcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWIzYzRcdWI4NWNcdWM3NTggXHViMDVkXHVhZTRjXHVjOWMwIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWIzYzRcdWI4NWNcdWM3NTggXHVjMmRjXHVjNzkxXHVjNzQwIDBcdWJiZjhcdWQxMzBcdWM3NzRcdWFjZTAsIFx1YjA1ZFx1Yzc0MCBMXHViYmY4XHVkMTMwXHVjNzc4IFx1YzljMFx1YzgxMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMmUwXHVkNjM4XHViNGYxXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVhY2ZjIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzQgTFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwgMSAmbGU7IEwgJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzJlMFx1ZDYzOFx1YjRmMVx1Yzc1OCBcdWM4MTVcdWJjZjQgRCwgUiwgR1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgRCAmbHQ7IEwsIDEgJmxlOyBSICZsZTsgMTAwLCAxICZsZTsgRyAmbGU7IDEwMCkgRFx1YjI5NCBcdWMyZTBcdWQ2MzhcdWI0ZjFcdWM3NTgmbmJzcDtcdWM3MDRcdWNlNThcdWM3NzRcdWJhNzAsIFJcdWFjZmMgR1x1YjI5NCBcdWJlNjhcdWFjMDRcdWMwYzksIFx1Y2QwOFx1Yjg1ZFx1YzBjOVx1Yzc3NCBcdWM5YzBcdWMxOGRcdWI0MThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZTBcdWQ2MzhcdWI0ZjFcdWM3NDAgRFx1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVhYzE5XHVjNzQwIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmUwXHVkNjM4XHViNGYxXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjNzc0XHVjMGMxIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWIwNWRcdWFlNGNcdWM5YzAgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI5ODAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTRU1BRk9SSSIsImRlc2NyaXB0aW9uIjoiPHA+THVrYSBpcyBkcml2aW5nIGhpcyB0cnVjayBhbG9uZyBhIGxvbmcgc3RyYWlnaHQgcm9hZCB3aXRoIG1hbnkgdHJhZmZpYyBsaWdodHMuIEZvciBlYWNoIHRyYWZmaWMgbGlnaHQgaGUga25vd3MgaG93IGxvbmcgdGhlIHJlZCBhbmQgZ3JlZW4gbGlnaHRzIHdpbGwgYmUgb24gKHRoZSBjeWNsZSByZXBlYXRpbmcgZW5kbGVzc2x5KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2hlbiBMdWthIHN0YXJ0cyBoaXMgam91cm5leSwgYWxsIHRyYWZmaWMgbGlnaHRzIGFyZSByZWQgYW5kIGp1c3Qgc3RhcnRlZCB0aGVpciBjeWNsZS4gTHVrYSBtb3ZlcyBvbmUgZGlzdGFuY2UgdW5pdCBwZXIgc2Vjb25kLiBXaGVuIGEgdHJhZmZpYyBsaWdodCBpcyByZWQsIGhlIHN0b3BzIGFuZCB3YWl0cyB1bnRpbCBpdCB0dXJucyBncmVlbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyBob3cgbXVjaCB0aW1lIEx1a2EgbmVlZHMgdG8gcmVhY2ggdGhlIGVuZCBvZiB0aGUgcm9hZC4gVGhlIHN0YXJ0IG9mIHRoZSByb2FkIGlzIGF0IGRpc3RhbmNlIHplcm8sIHRoZSBlbmQgYXQgZGlzdGFuY2UgTDxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEwgKDEgJmxlOyBOICZsZTsgMTAwLCAxICZsZTsgTCAmbGU7IDEwMDApLCB0aGUgbnVtYmVyIG9mIHRyYWZmaWMgbGlnaHRzIG9uIHRoZSByb2FkIGFuZCB0aGUgbGVuZ3RoIG9mIHRoZSByb2FkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgRCwgUiBhbmQgRywgZGVzY3JpYmluZyBvbmUgdHJhZmZpYyBsaWdodCAoMSAmbGU7IEQgJmx0OyBMLCAxICZsZTsgUiAmbGU7IDEwMCwgMSAmbGU7IEcgJmxlOyAxMDApLiBEIGlzIHRoZSBkaXN0YW5jZSBvZiB0aGUgdHJhZmZpYyBsaWdodCBmcm9tIHRoZSBzdGFydCBvZiB0aGUgcm9hZC4gUiBhbmQgRyBkZW5vdGUgaG93IGxvbmcgdGhlIHJlZCBhbmQgZ3JlZW4gbGlnaHRzIGFyZSBvbiwgcmVzcGVjdGl2ZWx5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdHJhZmZpYyBsaWdodHMgd2lsbCBiZSBvcmRlcmVkIGluIGluY3JlYXNpbmcgb3JkZXIgb2YgRC4gTm8gdHdvIHRyYWZmaWMgbGlnaHRzIHdpbGwgc2hhcmUgdGhlIHNhbWUgcG9zaXRpb24uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSB0aW1lIChpbiBzZWNvbmRzKSBMdWthIG5lZWRzIHRvIHJlYWNoIHRoZSBlbmQgb2YgdGhlIHJvYWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZmlyc3QgZXhhbXBsZSwgTHVrYSB3aWxsIHdhaXQgMiBzZWNvbmRzIGF0IHRoZSBmaXJzdCB0cmFmZmljIGxpZ2h0LiBBZnRlciB0aGF0IGhlIHdpbGwgcmVhY2ggdGhlIHNlY29uZCB0cmFmZmljIGxpZ2h0IHdoaWxlIGl0IGlzIGdyZWVuIGFuZCBiZSBhYmxlIHRvIHBhc3MgdGhyb3VnaCBpbW1lZGlhdGVseS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #6 2번