A highly anticipated examination is scheduled for tomorrow morning.

For the past week, social media has been flooded with rumors about leaked papers, secret answer keys, and "100% reliable sources."

The paper definitely wasn't leaked to you, so now you must actually study.

There are n chapters remaining in the syllabus.

For each chapter:

• time[i] represents the number of hours required to revise chapter i.
• marks[i] represents the marks you can gain by revising chapter i.

You have only h hours left before the exam.

You may revise a chapter at most once, and partial revision is not allowed.

Return the maximum total marks you can gain by selecting an optimal set of chapters to revise without exceeding the available time.

As the exam draws closer, you realize an important truth:

Platform may be banned, but your panic is still fully operational.

Example 1

Input

time = [2, 3, 1]
marks = [20, 30, 15]
h = 4

Output

45

Explanation

You can revise:

• Chapter 1 (3 hours, 30 marks)
• Chapter 2 (1 hour, 15 marks)

Total time used:

3 + 1 = 4

Total expected marks:

30 + 15 = 45

No other valid selection yields more marks.

Example 2

Input

time = [4, 2, 3]
marks = [50, 20, 40]
h = 5

Output

60

Explanation

Revise chapters 1 and 2.

Time = 2 + 3 = 5
Marks = 20 + 40 = 60

Although chapter 0 gives 50 marks, combining chapters 1 and 2 produces a better result.

Example 3

Input

time = [5, 6, 7]
marks = [10, 20, 30]
h = 4

Output

0

Explanation

There is not enough time to revise any chapter.

Constraints

1 <= n <= 1000
n == time.length == marks.length
1 <= time[i] <= 1000
1 <= marks[i] <= 1000
1 <= h <= 1000

Notes

• Each chapter can be revised at most once.
• Partial revision is not allowed.
• Expected marks are independent of one another.
• Rumors, forwarded messages, and "trust me bro" sources do not count as preparation.

Hint

The most time-consuming part of exam preparation is not studying.
It's deciding what not to study.

If you enjoyed the problem, consider an upvote!