선거에서 이기자 timer 2초 memory 1024MB

정올 공화국은 1번부터 N번까지 번호가 매겨진 주(state)들로 이루어져 있습니다.

2022년에는 정올 공화국에서 대통령 선거가 실시됩니다. 

선거는 각 주에서 실시됩니다. 한 주의 선거에서 승리한 후보는 해당 주의 표를 받습니다.

재민이는 대통령에 출마하여 승리할 계획입니다. 그의 계획은 신뢰도를 높이기 위해 연설을 하는 것입니다.

그가 연설을 한 후에는 다음과 같은 일이 일어날 것입니다.

• i번 주에서 총 연설 시간 A_i 시간을 달성하면, 그는 선거에서 승리해 i번 주의 표를 얻을 것입니다.

• i번 주에서 총 연설 시간 B_i 시간을 달성하면, 그는 i번 주에서 한 명의 지지자를 얻을 것입니다.

그 후 재민이의 지지자들은 재민이처럼 다른 주들로 가서 연설을 할 수 있게 됩니다.

물론 재민이가 주에서 지지자를 얻지 못할 수 있는데, 이 경우 B_i = -1로 표시됩니다. 그 외의 경우에는 항상 A_i \le B_i 임이 보장됩니다.

i번 주에서 온 지지자는 다른 주들에서 연설을 할 수 있으며, 한 명 이상의 사람이 같은 주에서 동시에 연설을 할 수 있습니다.

예를 들어 두 사람이 같은 주에서 x시간 연설을 하는 경우, 해당 주에서는 총 연설 시간이 2x 시간만큼 증가합니다.

연설 시간은 정수가 아닐 수 있고, 주들 사이를 이동하는 데 걸리는 시간은 무시합니다.

선거일이 곧 다가오기 때문에 재민이는 가능한 한 빨리 K개 주의 표를 확보하고 싶습니다.

주의 개수와 각 주의 정보가 주어졌을 때 K개 주의 표를 얻는 최소 시간을 계산하는 프로그램을 작성하십시오.​