Regional flights for me to France the last couple of years have similar tight allowances, I ended up buying a Lowepro Urban Reporter 250 but probably could have got the 350. Managed to fit in a couple of bodies and a handful of lenses, batteries chargers a change of clothes, tripod, cleaning kit for me and the camera, MacBook pro etc...
Of course you can always wear a jacket with a few pockets that are a little on the big side to hide lenses in and have a camera round your neck, that what I use to do when I was lugging about the bigger cameras, not such a big deal with the Fuji though. They never said anything and it kept the bag under the weight but I've never been asked to weigh it as it looks small. Bon chance.