Sequential Numbering Macro?

I have a large sheet (currently some 5,000 rows and growing) where each row is allocated a Unique Reference, however that unique reference is based on two criteria, 'Region' and 'Type'.

There are four 'Regions' and three 'Types' across the whole sheet (see attched sample).

Because of the ever increasing number of entries and the fact that the sheet may be sorted so the unique references won't always appear in sequential order, I am looking to try and find a way for the unique refrence for 'new entires' to the sheet to be generated automatically, based on entires in other columns. The sheet structure is relatively simple, with 'Region' shown in one column and 'Type' in another (again, see attached sample).

The unique references adopt this structure - 1st letter of the region (N, S, E or W for North, South, East or West), followed by 1415, followed by the first 4 characters from the 'Type', (REGI, NATI or COUN for Regional, National or County) followed by a sequential 5 digit number 00001, 00002, 00003 etc.

resulting in for example N1415REGI00001 or W1415COUN00012 and so on.

Because there are thousands of entries, I need an automatic way for the unique reference to be generated, ideally once both the 'Region' and 'Type' fields are populated, so the macro (or whatever method works best) will automatically determine the previous highest number for the relevant series and automatically add the next number for the new entry, based on the above criteria.

I don't know if this is possible with a macro or whether there is an easier formulaic way to achieve this?