빗자루를 다루는 이는 한 명의 아름다운 소녀, 검은 로브와 삼각 모자를 몸에 걸쳤고, 잿빛 머리카락은 바람에 흩날렸습니다.
그곳에 다른 누군가가 있었다면 분명 모두 돌아보며 한숨을 흘리고 말 정도의 미모를 겸비한 그녀는 대체 누구일까요?
그렇습니다. 바로 저입니다.
— 일레이나, 「마녀의 여행」
유명한 빵가게가 많은 나라가 근처에 있다는 소문을 듣게 된 저는, 재빨리 빗자루를 타고 그곳에 도착했습니다. 이 나라는 번 마을부터 번 마을까지 총 개의 마을로 이루어져 있고, 번 빵가게부터 번 빵가게까지 총 개의 빵가게가 존재합니다. 신기하게도, 이 나라의 빵가게들은 아래와 같은 특징이 있습니다.
제 초기 마력은 이고, 마력을 원하는 만큼 올릴 수 있지만 만큼 올릴 때마다 동화 개를 대가로 지불해야 합니다. 돈 계산은 머리 아픈 일입니다. 저 대신 모든 마을에서 빵을 적어도 한 번씩 구매하기 위해 필요한 동화 개수의 최솟값을 구해 주세요.
첫째 줄에 마을의 수 , 빵가게의 수 , 일레이나의 마력을 만큼 올리기 위해 필요한 동화의 수 가 공백으로 구분되어 주어진다.
두 번째 줄부터 줄에 걸쳐 번째 빵집이 위치한 마을의 번호 , 빵의 가격 , 필요한 마력 가 공백으로 구분되어 주어진다.
주어지는 입력은 모두 정수이고, 항상 모든 마을에서 빵을 구입할 수 있는 입력만 주어진다.
첫째 줄에 일레이나가 모든 마을에서 빵을 적어도 한 번씩 구매하기 위해 필요한 동화 개수의 최솟값을 출력한다.
일레이나의 마력이 일 때, 번 빵가게와 번 빵가게에서 빵을 구매하면 동화가 개 필요하고, 이 때 필요한 동화의 개수가 최소가 된다. 반드시 모든 빵가게에서 빵을 구매해야 하는 것이 아님에 유의하라.
