### Problem Statement

You are studying at a university, and there are many CS courses you can take. The i-th course is described by three values: theoreticalValue[i], practicalValue[i] and expire[i], where i is a 0-based index. Each course lasts one month, and you can not take the i-th course in the expire[i]-th month or later.

For each course i, let tvi = theoreticalValue[i] and pvi = practicalValue[i]. You can take the i-th course only if your theoretical skill is at least tvi-1 and your practical skill is at least pvi-1. If your theoretical skill is less than tvi, it will become tvi after you take the course. Similarly, if your practical skill is less than pvi, it will become pvi after you take the course.

Both your theoretical and practical skills are initially equal to 0, and you can start taking courses in the 0-th month. You can only take one class per month. Your goal is to have your theoretical and practical skills both be greater than or equal to skillBound. You want to achieve this by taking the fewest possible number of courses. Return a int[] containing the courses you should take, in order from earliest to latest. If there is no solution, return an empty int[]. If there are multiple solutions, return the one that comes earliest lexicographically. A int[] a1 comes before a int[] a2 lexicographically if a1 contains a smaller value at the earliest index at which they differ.

### Definition

 Class: CsCourses Method: getOrder Parameters: int[], int[], int[], int Returns: int[] Method signature: int[] getOrder(int[] theoreticalValue, int[] practicalValue, int[] expire, int skillBound) (be sure your method is public)

### Constraints

-theoreticalValue will contain between 1 and 50 elements, inclusive.
-theoreticalValue, practicalValue and expire will contain the same number of the elements.
-Each element of theoreticalValue will be between 0 and 50, inclusive.
-Each element of practicalValue will be between 0 and 50, inclusive.
-Each element of expire will be between 0 and 50, inclusive.
-skillBound will be between 0 and 50, inclusive.

### Examples

0)

 `{1}` `{1}` `{1}` `1`
`Returns: {0 }`
1)

 `{1, 2, 1}` `{2, 1, 1}` `{5, 5, 5}` `2`
`Returns: {2, 0, 1 }`
 You should take the courses in one of the following orders: {2, 0, 1} or {2, 1, 0}. The first one comes earlier lexicographically.
2)

 `{1, 2, 1}` `{2, 1, 1}` `{1, 1, 1}` `2`
`Returns: { }`
 In the 0-th month, the only course you can take is course 2. However, after you complete the course, all three courses will expire.
3)

 `{1, 2, 1}` `{2, 1, 1}` `{3, 2, 1}` `2`
`Returns: {2, 1, 0 }`
4)

 `{1, 2, 3, 4, 5, 6, 7}` `{1, 2, 3, 4, 5, 6, 7}` `{1, 2, 3, 4, 5, 6, 7}` `7`
`Returns: {0, 1, 2, 3, 4, 5, 6 }`
5)

 `{0, 1, 2, 2, 1}` `{0, 0, 1, 2, 1}` `{9, 9, 9, 9, 9}` `2`
`Returns: {4, 3 }`
 {0, 1, 2, 3} is a valid order, but we are looking for the fewest number of courses.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7505

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10664&pm=7505

Mike Mirzayanov

#### Testers:

PabloGilberto , brett1479 , Yarin , Olexiy

Graph Theory