Larry got a new job at a warehouse! His job is to package items into boxes, and move them into storage. Unlike most other warehouses, however, this warehouse is forward-thinking and promotes diversity. Because of this, Larry is tasked with maximizing diversity in the boxes he packages.

There are ~N~ items on a conveyor belt in front of Larry of which he must package. Larry must take the items off the conveyor belt in the order they are on the conveyor belt, or else he will mess up the automatic system. Each item has a size ~S_i~ and a type ~T_i~.

Since the warehouse promotes diversity, Larry must maximize the sum of the diversity of all the boxes that he packages. The diversity of a box is defined as the number of distinct types of items in the box.

However, there are some restrictions. Each box has a capacity of ~C~ (the sum of the sizes of the items in the box must not exceed ~C~). Since the warehouse is also Eco-Friendly, each box must have at least ~M~ sum of item sizes, as to not waste cardboard.

Input Specification

The first line will contain three integers: ~N\ (1 \leq N \leq 2\cdot 10^5)~, ~M~ and ~C\ (1 \leq M \leq C \leq 10^9)~.

The next line will contain ~N~ integers ~S_i\ (1 \leq S_i \leq C)~.

The final line will contain ~N~ integers ~T_i\ (1 \leq T_i \leq N)~

Output Specification

You are to output one line, the maximum diversity satisfying the constraints, or FIRED if Larry cannot package all the items, and loses his job.

Subtasks

Subtask 1 (30%)

~N \leq 3000~

Subtask 2 (70%)

No further constraints.

Sample Input

5 5 14
7 8 3 2 2 
1 1 3 3 4

Sample Output

4